백준 알고리즘 1463번: 1로 만들기 [C++]

문제 출처: www.acmicpc.net/problem/1463

1463번: 1로 만들기

1. 코드

#include <iostream>
#include <algorithm>

using namespace std;
int dp[1000001] = { 0, };
int main(void)
{
	int n;
	cin >> n;

	for (int i = 2; i <= n; i++)
	{
		dp[i] = dp[i - 1] + 1;	//2와 3으로 나누어지지않는 경우
		if (i % 2 == 0) dp[i] = min(dp[i], dp[i / 2] + 1);	//2로 나누어지는 경우
		if (i % 3 == 0) dp[i] = min(dp[i], dp[i / 3] + 1);	//3으로 나누어지는 경우
	}
	cout << dp[n];
}

(실행)

2. 풀이

프로그램 과정

프로그램 과정 같은 경우 위 gif와 같이 움직이는데 N = 6일 경우 -1이 되는 경우, 그리고 2로 나누는 경우 3으로 나누는 경우 이렇게 계속해서 1이 될때까지 펼치고 N = 1일 경우는 0이다. 그리고 N = 2일 경우는 1이고, N = 3일 경우는 3이다. 그런데 이것을 식으로 나타낸다면 N = 4일 경우는 2일 것이다. 그렇다면 N = 4일 때 N = 2일 경우와 N = 3일 경우로 나누어지고 그 중에서 제일 작은 값을 고르고 +1한 값으로 N = 4일 경우가 정해진다. 그것을 식으로 만들면 dp[4] = min(dp[4 - 1], dp[4 / 2]) + 1이다.

N = 6일 경우는 위 gif를 참고하면 dp[6] = (dp[6 - 1], dp[6 / 2], dp[6 / 3]) 중 제일 작은 결과 + 1이다. 그리고 N = 5일 경우는 2와 3으로 나눌 수 없기 때문에 이러한 경우도 생각을 하여 처음부터 dp[5] = dp[5 - 1] + 1와 같은 식을 미리 만들어줍니다. 그리고 최종적으로 dp[n]을 출력하면 된다.

3. 느낀 점

계속해서 동적 계획법을 풀어보아도 유도되는 과정이 전혀 이해가 되지않고 이번 문제 또한 그랬다. 하지만 이렇게 그림으로 펼치고 점차 공통된 부분을 찾고 줄여보니 동적 계획법에 대해 조금은 알게된 기분이다.