https://www.acmicpc.net/problem/1463
문제
알고리즘 접근 방법
DP의 bottom-up 방식을 사용한다.
시간 복잡도는 O(N)
N+1 크기의 배열을 만들고 dp[1] = 0으로 초기화 해준다.
N까지 dp 배열을 채워나간다.
- X가 3으로 나누어 떨어지면 3으로 나눈다.
- X가 2로 나누어 떨어지면 2로 나눈다.
- X가 1로 뺀다.
다음 중의 3가지 연산 중 최솟값을 dp배열에 저장해나가면 된다.
ex. N=4
dp[4] = min(dp[4/3] + 1, dp[4/2] + 1, dp[4-1] + 1)
이 때 4는 3으로 나누어 떨어지지 않으므로 dp[4/2] + 1, dp[4-1] +1 중 최솟값을 저장
dp[4/2] + 1 = dp[2] + 1 = 2
dp[4-1] + 1 = dp[3] + 1 = 2
고로 dp[4] = 2가 출력된다.
ex. N=10
dp[10] = min(dp[10/3] + 1, dp[10/2] + 1, dp[10-1] + 1)
이 때 10은 3은 나누어 떨어지지 않으므로 dp[10/2] + 1, dp[10-1] +1 중 최솟값을 저장
dp[10/2] + 1 = dp[5] + 1 = 4 (dp[5] = dp[4] + 1 = 3)
dp[10-1] + 1 = dp[9] + 1 = 3 (dp[9] = min(dp[3], dp[8]) + 1 = dp[3] + 1 = 2)
고로 dp[10] = 3이 출력된다.
풀이
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
int N = 0;
cin >> N;
int dp[N+1] = {0, };
// 작은 값 바텀업 형식으로
dp[0] = 0;
dp[1] = 0;
for(int i=2; i<=N; i++){
dp[i] = dp[i-1] + 1; // 1로 빼보고 일단 저장
if(!(i%3)) dp[i] = min(dp[i], dp[i/3]+1); // 3으로 나눠지면 1로 뺀거랑 비교 해서 최솟값
if(!(i%2)) dp[i] = min(dp[i], dp[i/2]+1); // 2으로 나눠지면 1로 뺀거랑 비교 해서 최솟값
}
// 그렇게 N까지 반복해서 연산 결과 출력
cout << dp[N] << endl;
return 0;
}
정리
DP를 더 잘.. 쓰는 방법을 배워나가야겠다.
점점 이상하게 생각해나가서 검색해 보았는데 쉽게 푸셔서 도움이 많이 되었다.
