Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 | 31 |
Tags
- 1748번
- 11053번
- 2504번
- LIS
- C++
- 1759번
- 그리디
- 1120번
- 수 이어쓰기 1
- 스택
- 1918번
- 1004번
- 209번
- 릿코드
- 3086번
- 트리 구현
- 1029번
- 구현
- 배열
- 1931번
- LeetCode
- 2293번
- 2503번
- 자료구조
- 투포인터
- 백준
- 2565번
- 1874번
- 7569번
- 최소힙
Archives
- Today
- Total
Hello World!
[BOJ] 2565번: 전깃줄 본문
문제 링크: 백준/BOJ https://www.acmicpc.net/problem/2565
LIS 문제였다.
LIS에 대한 자세한 설명은 아래 글에 있다.
https://hellooworld.tistory.com/21
단, 배열에 대한 인덱스가 0부터 n까지 차례로 있는게 아니라서
전봇대의 위치 번호의 최대값인 500까지 인덱스로 받을 수 있도록
배열 크기를 501로 설정해주었다.
또한 처음에 배열 값은 모두 0으로 설정되어 있고,
전봇대의 위치 번호는 자연수이므로 배열 값이 0인 경우는 A와 B 사이에 전깃줄이 없다는걸 의미한다.
전깃줄 개수(n)에서 LIS 길이를 빼주면 우리가 없애야 하는 전깃줄 개수를 구할 수 있다.
/*
20200512
baekjoon 2565번 - 전깃줄
*/
#include <iostream>
#include <algorithm>
using namespace std;
int arr[501], dp[501];
int main() {
cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
int n, M = 0;
cin >> n;
for (int i = 0; i < n; ++i) {
int idx, val;
cin >> idx >> val;
arr[idx] = val;
}
for (int i = 1; i <= 500; ++i) {
if (arr[i] == 0) continue;
dp[i] = 1;
for (int j = 1; j < i; ++j) {
if (arr[i] > arr[j] && dp[i] < dp[j] + 1) {
dp[i] = dp[j] + 1;
if (M < dp[i]) {
M = dp[i];
}
}
}
}
cout << n - M;
}
'알고리즘 > baekjoon' 카테고리의 다른 글
[BOJ] 7569번: 토마토 (0) | 2020.05.17 |
---|---|
[BOJ] 2293번: 동전 1 (0) | 2020.05.16 |
[BOJ] 11053번: 가장 긴 증가하는 부분 수열 (0) | 2020.05.12 |
[BOJ] 1759번: 암호 만들기 (0) | 2020.05.10 |
[BOJ] 1748번: 수 이어 쓰기 1 (0) | 2020.05.09 |
Comments