정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.
- X가 3으로 나누어 떨어지면, 3으로 나눈다.
- X가 2로 나누어 떨어지면, 2로 나눈다.
- 1을 뺀다.
정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.
예제 입력 1 복사
2
예제 출력 1 복사
1
예제 입력 2 복사
10
예제 출력 2 복사
3지금 이문제 2시간동안 고민하고있는데 뭔가 재귀적으로 푸는문제같은데 어떻게 해야할지 모르겠어요 팁좀 주십셔 ㅠ
간단한 dp 문제, 인터넷에서 dp를 배워요
저도 살짝 해봤는데 전 처음에 3으로 나누고 안되면 2로 나누고 그것도안되면 1빼고 이렇게 하면 1에 최대한 빨리 갈수있으니까 이런식으로 시도했는데 10같은경우가 반례더라고여... 거기부터 머리가 대혼란이 오네요.
정수 n을 1로 만드는 최소횟수를 cache[n] 이라고 하면, cache[n-1]+1 cache[n/2]+1 cache[n/3]+1 중 최솟값을 취하면 됨