[102일차] 1로 만들기 - 백준 - 1463(python - 다이나믹 프로그래밍)

문제 설명

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

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

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

 

입력

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

 

출력

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

 

예제 입력, 예제 출력

2	1
10	3

 

코드 및 설명

x = int(input())
dp = [0] * (x+1)

for i in range(2,x+1):
  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)
    
print(dp[x])

 

이 문제는 DP 문제이다. 분명 프로그래머스에서도 이런 비슷한 문제를 풀었던 기억이 있는 데 그땐 좀 제대로 이해를 하지 

 

못하고 넘어갔던 것 같다. 지금 단순 while문으로 if x % 3 == 0 일때 이런식으로 코드를 짜보았으나, 계속 틀렸었다.

 

그래서 DP관련해서 찾아보게 되었는 데, 2가지 방식으로 일단 풀 수 있는 것 같다.

 

DP - Bottom Up , DP - Top Down 2가지이다.

 

Bottom up은 반복문 - 작은 문제부터 시작해서 큰 문제까지 모두 답 찾는 방식

 

Top Down은 재귀함수를 사용 - 큰 문제부터 작은 문제로 쪼개지며 답을 찾는 방식

 

DP 문제들은 최대화 / 최소화 계산을 하거나 특정 조건 내 데이터를 구해야하거나 확률 등의 계산의 경우 DP로 풀 수 있는

 

경우가 많다고 한다.

 

	1	2	3	4	5	6	7	8	9
min	0	1	1	2	3	2	3	3	2
+1	0	1	2	2	3	4	3	4	4
*2		1		2		2		3
*3			1			2			2

 

위에 표를 보면 +1, *2, *3 조건이니까 1은 무조건 되니까 0이고, 2는 1에서 2로 가야하는 데 +1하면 2가 되기때문에 1의

 

min값인 0 + 1, 2는 +1을 할때 1번 계산하면 1이 될 수 있고, *2도 마찬가지 1의 값에 2를 곱하면 2가 되기 때문에 1번 계산

 

으로 구할 수 있다. 그래서 min은 1이 된다. 3은 이제 +1하는 조건에선 2의 값이 1번 계산하면 되는거였고, 3이 되려면

 

+1을 한번 해주면 되기 때문에 2의 min인 1 + 1해주면 2번 계산으로 3이 될수 있다. 곱하기 2는 해당이 안되기 때문에 패스

 

하고, *3에서는 1번이면 3을 만들 수 있기 때문에 1이 된다. 이런식으로 작은 문제에서 큰 문제로 올라가면 답을 구할 수 있

 

게 된다.