[백준] 1463번: 1로 만들기 [C++]

알고리즘 분류: 다이내믹 프로그래밍

문제 링크: https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

 

 

 

【 풀이 】

 

동적 계획법(DP, Dynamic Programming)을 이용하여 해결하는 문제이다.

그리고 이 문제 역시 여러 경우의 수를 생각하며 규칙성을 찾는 것이 중요한데, 이 규칙을 찾는 것이 어려웠던 것 같다.

 

우선 index를 피연산수, 값을 연산 횟수로 배열을 선언한 다음

1~10까지의 수를 검사하며 규칙을 찾아나갔는데, 규칙은 대충 다음과 같이 나왔었다.

 

• 2와 3으로 모두 나누어 떨어지지 않는 수: 1 + dp[index - 1]
• 2와 3으로 모두 나누어 떨어지는 수: 1 + dp[index/2] 또는 1 + dp[index/3]  (둘 중  최솟값)
• 2로만 나누어 떨어지는 수: 1 + dp[index/2] 또는 1 + dp[index-1]  (둘 중 최솟값)
• 3으로만 나누어 떨어지는 수: 1 + dp[index/3] 또는 1 + dp[index-1]  (둘 중 최솟값)

위 규칙을 적용하여 처음부터 시작해서 값을 채워나가는 Bottom - Up 방식으로 구현했다.

 

 

 

 

【 코드 】

 

#include<iostream>
using namespace std;

int cal[1000001];
int main(void)
{
	int cnt = 0;
	int n;
	cin >> n;
	cal[1] = 0; cal[2] = 1; cal[3] = 1;
	for (int i = 4; i <= n; i++)
	{
		if (i % 2 != 0 && i % 3 != 0) 
			cal[i] = 1 + cal[i - 1];

		if (i % 2 == 0 && i % 3 == 0) 
			if (1 + cal[i / 2] < 1 + cal[i / 3]) 
				cal[i] = 1 + cal[i / 2];
			else 
				cal[i] = 1 + cal[i / 3];

		if (i % 2 == 0 && i % 3 != 0) 
			if (1 + cal[i / 2] < 1 + cal[i - 1]) 
				cal[i] = 1 + cal[i / 2];
			else 
				cal[i] = 1 + cal[i - 1];
			
		if (i % 3 == 0 && i % 2 != 0) 
			if (1 + cal[i / 3] < 1 + cal[i - 1]) 
				cal[i] = 1 + cal[i / 3];
			else 
				cal[i] = 1 + cal[i - 1];
	}
	cout << cal[n];
	return 0;
}