[동적계획법, 난이도 중] 백준 11053번 가장 긴 증가하는 부분 수열
제한 시간은 1초며, N의 범위가 (1 ≤ N ≤ 1,000) 으로 좁은 편이기 때문에 O(N^2) 까지 쓸 수 있다. 그래도 이 문제는 1차원 배열의 DP로 풀 수 있다. 첫 INPUT에 대한 DP의 첫 인덱스 값을 1로 두며 시작한다. 그리고 이 조건에 따라 뒤 INPUT값들에 대해 DP를 수행해주면 된다. 현재 INPUT값보다 작은 모든 이전 INPUT값들의 각 DP값들중 최댓값에 1을 더한 값을 현재 DP값으로 지정한다. 만약 현재 INPUT값이 30이라면 이전 INPUT값들은 각각 10, 20, 10이고, 이들의 각 DP값은 1,2,1이다. 1,2,1의 최댓값은 2이기 때문에 이에 1을 더한 3을 현재 DP값으로 지정하는 것이다. 현재 INPUT값이 지금까지 나온 INPUT값들중 최솟값일 경우가..
2020. 8. 24.
[그리디, 난이도 중하] 백준 2217번 루프
n개의 연결된 루프에 매댈 수 있는 최대 무게를 구할 수 있어야 한다. 이 문제의 예제는 부실하므로 버틸 수 있는 최대 중량이 각각 7, 15, 30, 11, 5인 루프 5개를 준비하였다. 일단 이 루프를 내림차순으로 정렬했다. 30, 15, 11, 5, 7 먼저 최대 중량이 30인 밧줄은 당연히 중량이 30인 물체까지 버틸 수 있다. 그렇다면 1,2번째로 최대 중량이 높은 밧줄인 30, 15를 묶으면 어디까지 버틸 수 있을까? k개의 루프가 묶인다면 중량은 k분의 1로 나뉘게 된다고 했다. 2번째로 최대 중량이 높은 15에 2를 곱한 30이 최대가 된다. 중량이 30인 물체는 저 밧줄들에 각각 15, 15씩 분배가 되므로 30이 최대가 된다는 것을 검산했다. 그렇다면 1,2,3번째로 최대 중량이 높은 ..
2020. 8. 22.
