문제 링크 : 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)
로 해야 정답이 나온다
'알고리즘 > DP' 카테고리의 다른 글
백준 2839번 : 설탕 배달 (0) | 2021.06.26 |
---|---|
백준 2565번 : 전깃줄 (0) | 2021.02.03 |
백준 2342번 : Dance Dance Revolution (0) | 2021.02.01 |
백준 10844번 : 쉬운 계단 수 (0) | 2021.01.30 |
백준 11660번 : 구간 합 구하기 5 (0) | 2021.01.29 |