알고리즘/DP
백준 1463번 : 1로 만들기
Jason95
2021. 6. 26. 18:43
문제 링크 : https://www.acmicpc.net/problem/1463
풀이에 참고한 링크 : https://www.acmicpc.net/board/view/66915
내 풀이(2021.6.26.) : DP
#include <iostream>
#include <algorithm>
using namespace std;
int dp[1000000];
int main() {
int N; cin >> N;
for (int i = 2; i <= N; i++)
{
dp[i] = 1000001;
}
dp[1] = 0;
for (int i = 2; i <= N; i++)
{
dp[i] = min(dp[i], dp[i - 1] + 1);
if (i % 2 == 0) dp[i] = min(dp[i], dp[i / 2] + 1);
if (i % 3 == 0) dp[i] = min(dp[i], dp[i / 3] + 1);
}
cout << dp[N];
return 0;
}
if(i%2==0)
else if(i%3==0)
로 하면 오답이 나오고
if(i%2==0)
if(i%3==0)
로 해야 정답이 나온다