백준 1463문제 파이썬 (dynamic programming알고리즘)

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

1463번: 1로 만들기

나만 어려운 문제일 수 있다 ㅎㅎ

피보나치문제는 되게 간단하던데 이 문제는 답지를 봐도 이해가 안되어서 하나하나 적으면서 풀어봤다.

 

이해가 안갔던 이유:

계산한 값들을 배열에 저장해야된다고 생각했다. 

숫자가 인덱스라는 점이 안 와 닿았다. 

 

코드 보면서 얘기해보자~~

 

먼저 dp 다이나믹 프로그래밍은

반복적인 계산을 효율적으로 처리를 하는 알고리즘이다. 

큰문제를 작은 문제로 나누어 해결하고 그 결과를 저장해놨다가 재사용하여 중복계산을 피한다.

 

피보나치 보면 이해가 바로 가능하다

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

n = int(input())
#앞서 계산된 결과를 저장하기 위한 DP테이블 초기화
#n번째
d = [0]* (n+1)
print("d:",d)
#피보나치 수 : 0, 1, 1, 2, 3, 5....
#0,1로 시작하는 값
#인덱스 1번째 1  
d[1] =1
#반복문은 2번째부터 시작. 
for i in range(2, n+1): #2~n까지
	#1= 1+0
    d[i] = d[i-1]+ d[i-2]
    print(d[n])

 

처음 0,1을 주고 시작함!

그러면 인덱스 2, 부터 계산됨

 

 

그렇다면 이 문제.

 

 

피보나치는 더한 값들을 배열 d에 기록해서 간단했는데

이문제는 구하고자 하는 값이 횟수이다. 횟수를 기록해야한다.

 

숫자 10이 몇 번의 횟수를 거쳐 1이 되었냐~ 는 문제이다.

이 숫자 10과 횟수의 관계를 코드로 정립 못했었다..

횟수를 기록한 d배열의 인덱스가  "주어진 숫자" 역할을 했다. 그게 잘 안와닿았다.

 

즉 인덱스 3은 숫자 3. 그러면 인덱스 3에 횟수를 기록하게 되는 것이다. 

 

횟수를 기준으로 하니, 현재 횟수가 이전횟수 + 1이다라는게 겨우 이해되었다.

 

숫자가 2나 3으로 나눠지는 경우 : 예) 숫자가 6이면 "이전5의 횟수+ 1"을 하면 4가 되는데, 숫자 6은 2로 나눠지기때문에
최솟값으로 비교를 한다. "이전5의 횟수+ 1"  과 "d[6//3] 즉 d[2] 숫자2의 횟수에 1을 더한 값"을 비교하는 것이다.

나는 하나하나 값 넣어서 적어보면서 이해했다 ㅎㅎㅎ

# 답지
# n = int(input())
n = 10
print('n',n)
 
#계산한 횟수를 저장하는 용이래!!!
d = [0] * (n+1) 
print("d",d)

for i in range(2, n+1):  #2부터하는이유는0,1은 나누어떨어지지 않아서 횟수가 걍 0이라서!
    d[i] = d[i-1] +1 #더하기 1을 하는 이유는 기존횟수느 = 이전 횟수에 + 1 식 늘어나니까. 
   #i가 3으로 나눠지는 값이면 
    if i %3 == 0:
        #숫자 3의 횟수는 = 이전 횟수에 하나더한 횟수거나, 3으로 나눈 값의 횟수에 하나 더한 횟수! 둘중에 더 작은 값!
        d[i] = min(d[i], d[i//3]+1)
        print("3d[i]:", d[i])
    if i%2 == 0:
        d[i] = min(d[i], d[i//2]+1)

 
print(d[n])