[백준 #1463, Python] 1로 만들기

DP..거의 첫도전..사실 아직 잘 모르겠다.. 점화식 처럼 맨 하단에있는 값 부터 가지고 내 목표 값에 도달하게 만든다는 것 이외에는,,, 재귀랑 반대,, bottom-top인가,..? 아,, 넘 어렵다,,광광

[풀이]

from sys import stdin
n = int(stdin.readline())
dp = [0]*(n+1)
for i in range(2,n+1):
    if not i % 2 and not i % 3:#공배수일경우에는 3가지 조건을 다 비교해야한다.
        dp[i] = min(dp[i-1]+1,dp[i//2]+1,dp[i//3]+1)
    elif not i % 3: #3으로 나누어진다면
        dp[i] = min(dp[i-1]+1,dp[i//3]+1) #1을 더해주는 거랑, 3을 나눠주는 횟수랑 비교
    elif not i % 2:
        dp[i] = min(dp[i-1]+1,dp[i//2]+1)
    else:
        dp[i] = dp[i-1] + 1
print(dp[n])

 

원래 나의 brain 🌻 이라면 n을 무작정,,,3으로도 나눠보고,, 해서 1로 도착할때 까지 CNT를 구했겠지? 그런데 DP를 쓸려면 방식이 좀 다르다. 일단, 이건 숫자니까 숫자값을 idx로 하는 dp list를 만든다. 그러고 나는 원하는 값만 하는 줄 알았는데, 그냥 1~ n까지 다 돌려버린다. (이건 아마 내가 dp를 몰라서 그런 걸 수도). 

그런데, 즉 한 범위안의 숫자 i를 만들기 위해선는 방법이 3가지가 있는데, 3의 배수이거나, 2의 배수이거나, 1을 더해주는 것이다. 그리고 기존의 값과 비교해서 더 작은값을 추가해준다.

만약 9를 만들기 위해서는 1->3->9의 방식이거나, 1->2->4->8->9 와 같은 방식이 존재하는거시다.. 

즉 1->3->9 방식에서는 3을 만들기위해서는 1을 3배하는 방식을 채택하는게 가장 최소의 방법이므로, dp[3] = dp[1] + 1이 되는 거고, 여기서 dp[9] = dp[3] + 1의 방식으로 구하면 된다..

아.. 넘 어렵따..그래도 뿌듯 ;ㅂ;