백준 1463번/ 1로 만들기 with 동적계획법 (+백트랙킹)

0.15 초

128 MB

290644

98727

62985

32.865%

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

 

 

접근 방법

1. 백트랙킹

 

백트랙킹 트리 형태로 내려가다가 연산 횟수가 최소 횟수보다 같거나 크다면 가지치고 올라간다. 

n==1이 되는 순간 count를 최솟값으로 갱신하고 가지치고 올라간다. 

일반적인 백트랙킹의 탐색 방법인 DFS가 명시적으로 나타나지 않고 재귀와 가지치기만으로 구성됨. 

 

 

 

2. 동적계획법

 

동적계획법을 사용할 거면 점화식을 잘 세우는 것이 가장 중요하다. 

기본적으로 모든 경우에 적용 가능한 세 번째 연산(-1)을 고려하면, n의 연산 횟수는 n-1의 연산 횟수보다 1 더 크다.

dp[i] = dp[i-1]+1 

 

아래 코드는 동적계획법 중에서도 Tabulation 방법을 사용하고 있다. 

 

1. 메모이제이션 방법: 하향식 접근 방법 (top-down)

• 함수 호출 시 이전에 계산한 값을 기억하여 중복 계산을 피함.
• 필요한 값만 저장하고 불필요한 계산을 방지함.
• 재귀적인 구조를 가질 수 있음.

2. 탭(Tabulation) 방법: 상향식 접근 방법 (bottom-up)

• 반복문을 사용하여 작은 문제부터 큰 문제까지 차례대로 해결.
• 배열을 사용하여 중복 계산을 피하며, 필요한 값을 저장.
• 순차적인 계산으로 메모리를 더 효율적으로 사용할 수 있음.
• 보통 반복문을 사용하기 때문에 재귀를 사용하지 않음.