[백준 1463] -1로만들기(C++)/다이나믹 프로그래밍

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

1463번: 1로 만들기

 

접근은 잘 했는데 경우의 수를 각각 비교해서 최솟값으로 답을 내야한다는 점을 간과해서 한참 헤맨 문제이다. 내가 생각한 접근 방법은 아래와 같다. 

 

각 수를 1로 만드는 경우를 나열해 보았다.

입력	1	2	3	4	5	...	8	9	10
연산 횟수	0	1	1	2	3	...	3	2	3

점화식은 아래와 같이 세웠었다.

• n=1이면 0
• 3으로 나눠질 때 : f(x)=1+f(x/3)
• 2로 나눠질 때 : f(x)=1+f(x/2)
• 두 수로 나눠지지 않을 때 : f(x)=f(x-1)+1

 

이런식으로 세웠었다. 적용해보면 f(5)=1+f(4)=1+2=3 이런식으로 말이다. 그런데 10의 경우 위 방법으로 계산을 하면 f(10)=1+f(5)=4가 나온다. 이 방법보다는 f(10)=1+f(9)=3이 더 빠르다. 그래서 이런 경우를 해결하기 위해서는 가능한 방법으로 다 구해본 뒤 둘 중 최솟값을 채택해야 한다. 그렇게 한 코드는 아래와 같다.

 

#include <iostream>
using namespace std;
int arr[1000001];

int init = 0;

int number(int x) {
	if (x == 1) {
		return 0;
	}
	if (arr[x] != 0) {
		return arr[x];
	}

	int res= 1 + number(x - 1);
	if (x % 3 == 0) res = min(res, 1 + number(x / 3));
	if (x % 2 == 0) res = min(res, 1 + number(x / 2));
	arr[x] = res;
	return res;
	

}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	arr[2] = 1;
	arr[3] = 1;
	cin >> init;

	cout << number(init);


}