알고리즘/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)

로 해야 정답이 나온다