백준 1463번 - 1로 만들기 (C++/ DP - 동적계획법)

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.
X가 3으로 나누어 떨어지면, 3으로 나눈다.X가 2로 나누어 떨어지면, 2로 나눈다.1을 뺀다.
정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

 

접근법

실버3이라 무시했는데 생각보다 방법이 안 떠올랐다..
반복문을 끝도 없이 사용하면.. 뭐 풀수야 있겠지만 이 문제의 제한시간은 0.15초 이다.
수는 1,000,000 까지 들어오는 마당에 모든 경우의수를 무작정 테스트해보기엔 코드도 비효율적이고, 시간도 오래걸린다.
막막할때는 일단 경우의 수부터 적어보자

20구한다 가정

• 3일때 -> 3으로 나눈다 -> 끝
• 4일때 -> 1을 뺀다-> 3으로 나눈다 -> 끝 ( 3일때 사용)
• 5일때 -> 1을 뺀다-> 2로 나눈다-> 1을 뺀다 끝 (4일때 사용)
• 6일때 -> 3으로 나눈다 -> 2로나눈다 -> 끝 (2일때 (1) 사용)
• 7일때 -> 1을 뺀다 -> 3으로 나눈다 -> 2로 나눈다 -> 끝 (6일때 사용)
• ....
• 20일때 -> 2나누기 -> 2나누기 -> 1빼기 -> 2나누기 -> 1빼기 (10일때 사용)

일단 최소값을 찾으려면 모든 값을 돌아야하는것은 명확하다.  특정 공식이 있다면 상관없지만 이번문제에 한해선 공식을 적용할 여지는 보이지 않는다.
일단 20을 구한다 가정했을때 이전에 구한 최소값을 참조하면 비교횟수를 엄청 줄일 수 있다.
solution은 아래부터 최소값을 천천히 구해서 올라가는것이라 생각했고, ( 상위는 하위에 구한 값을 그냥 가져오면 됨) cache에는 각 수가 1까지 가는 연산이 몇번걸리는지 저장했다.
 

코드

#include <iostream>
using namespace std;

int cache[1000000];

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cache[2] = 1;

	int N;
	cin >> N;
	for (int i = 3; i <= N; i++)
	{
		cache[i] = cache[i - 1] + 1; // 일단 1뺀 값부터 시작한다 가정한다

		if (i % 2 == 0)
		{// 2로 나누어 떨어진다면
			cache[i] = min(cache[i / 2] + 1, cache[i]); // 이 두가지 케이스중 이전에 더 작은값으로 접근
		}
		if (i % 3 == 0)
		{ // 3으로 나누어 떨어진다면
			cache[i] = min(cache[i / 3] + 1, cache[i]);
		}
	}
	cout << cache[N];
	
}

실버 3이라 무시하고 접근했는데 생각보다 어려웠다... 이런 문제는 여러번 풀어보고, 부딛혀 봐야할거같다.