[동적계획법, 난이도 중] 백준 2293번 동전 1
동전 i(1≤i≤n)개를 쓰며, j(0≤j≤10) 원을 만드는 모든 경우에 대해 DP를 수행해주면 된다. 예제 입력1에 대해 표를 만들어 보았다. 먼저, 1원 동전으로 0원부터 10원을 만드는 경우의 수는 모두 1이다. 2원 동전으로 0,1원을 만들 수는 없으므로 갱신하지 않고 그대로 1을 따라간다. 2원 동전으로 2원 이상을 만들 때부턴 새로운 경우가 발생한다. 1,2원 동전으로 j-2원을 만드는 경우의 수를 현재 값에 더해주면 되는데, 1,2원 동전으로 j-2원을 만드는 경우들에 2원 동전 하나만 더 추가하면 j원이 완성되기 때문에 이 경우들을 추가해주는 것이다. 1,2,5원 동전을 모두 사용하는 경우에도 똑같이 이를 적용해보자. 5원 동전으로는 5원 이상을 만들 때부터 새로운 경우가 발생한다. 1,..
2020. 8. 30.
[동적계획법, 난이도 중] 백준 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.
