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

https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

 

동적프로그래밍 첫문제이다. 처음에 그냥 손가는데로 풀어보기로 했다. (좋은 습관은 아니다.)

 

#include <iostream>
using namespace std;
 
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
 
	int n, cnt = 0;
	cin >> n;
 
	while (n != 1) {
		if (n % 3 == 0) {
			n /= 3;
		}
		else if (n % 2 == 0) {
			n /= 2;
		}
		else
			n -= 1;
		cnt++;
	}
 
	cout << cnt;
 
	return 0;
}

3으로 나누는게 최선인거 같아서 차례대로 if문을 만들어 해결하였지만 역시나 실패

 

이유는 n = 10이 주어졌을때 내가 푼 방법대로 하면 n = 5 -> n = 4 -> n = 2 -> n = 1 총 4번이 걸리지만

n = 9 -> n = 3 -> n = 1 총 3번에 1을 만드는 방법이 존재하기 때문

 

여기서 사용해야하는 방법은 DP(Dynamic Programming, 동적프로그래밍) 방식이다. 

 

하나의 문제를 여러개의 작은 문제로 나누어서 그 결과를 저장하여 해결하는 방식이다.

 

이 문제 또한 작은 문제로 나누어서 풀면 되는데 규칙을 찾아내야 하므로 1부터 어떠한 방식으로 숫자가 증가할때 계산 횟수가 증가하는지 살펴보자

 

1 = 1, 총 0회

 

2 = 2 / 1, 총 1회

 

3 =  3 / 1, 총 1회

 

4 = 4 / 2 / 2 or 4 - 1 / 3 , 총 2회

 

5 = 5 - 1 / 2 / 2, 총 3회 

 

6 = 6 / 2 / 3, 총 2회

 

7 = 7 - 1 / 2 / 3, 총 3회

 

8 = 8 / 2 / 2, 총 3회

 

9 = 9 / 3 / 3, 총 3회

 

10 = 10 - 1 / 3

 

여기까지 살펴보고 규칙을 찾아본다면

 

점화식이

d[i] = d[i / 2] + 1

 

d[i] = d[i / 3] + 1

 

d[i] = d[i - 1] + 1

이렇게 되고 이중에서 가장 작은 값을 선택하면 된다.

 

#include <iostream>
#include <algorithm>
using namespace std;
 
int dp[1000000];
 
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
 
	int n;
	cin >> n;
 
	for (int i = 2; i <= n; i++) {
		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;
}

 

전체 코드의 구성은 이렇다.

 

DP를 이해하는 첫 문제였지만 이해하기 조금 어려운 부분이 있어서 다른 문제를 더 풀면서 사용법을 익혀봐야겠다.