[백준/파이썬3/1463] 1로 만들기

풀이

x = int(input())
dp = [0 for _ in range(x+1)]
dp[1] = 0
for i in range(2, x+1):
    dp[i] = dp[i-1]+1
    if not i%2 and dp[i]>dp[i//2]+1:
        dp[i] = dp[i//2]+1
    if not i%3 and dp[i]>dp[i//3]+1:
        dp[i] = dp[i//3]+1
print (dp[x])

우선, Dp문제 이해가 안갔다. 유튜브 영상 몇개 보면서 감이 오는거 같긴했는데...... 머리가 평균이하인듯 ;ㅅ;

그래서 아나콘다에서 Spyder라는 툴을 이용해서 배열에 들어가는 값을 시각화 해보았다.

이해가 안가신다면 코드를 빤히 10분만 쳐다보시면 뭔가가 보일 것이다.

우선 index의 숫자를 보시면 예를 들어서 4를  2로 2번 나누어서 1로 만들수 있다 그러면 2번의 연산을 거치는게 배열의 값으로 들어가는 것을 볼수있다.

5의 경우는 5-> 4 -> 2 -> 1 이렇게 3번의 연산을 거치므로 index 5에는 3이라는 값이 들어가는 것을 볼 수 있다.

 

이런식으로 바라보면서 코드를 분석하면 이해가 쉽게 될 것이다.