240404 [BOJ/백준] 1463. 1로 만들기

 

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

1463번: 1로 만들기

---

나의 코드

N = int(input())

dp = [0]*1000001
for i in range(2, N+1):
    # 1씩 더하면서 dp에 저장
    dp[i] = dp[i-1] + 1

    # 2로 나눠지는 수는 2로 나눈 수에 해당하는 횟수에 1을 더한 값과 1을 뺀 수에 해당하는 횟수에 1을 더한 값의 최솟값을 저장
    if i % 2 == 0:
        dp[i] = min(dp[i], dp[i//2]+1)

    # 3으로 나눠지는 수는 3으로 나눈 수에 해당하는 횟수에 1을 더한 값과 1을 뺀 수에 해당하는 횟수에 1을 더한 값의 최솟값을 저장
    if i % 3 == 0:
        dp[i] = min(dp[i], dp[i//3]+1)

print(dp[N]) #N의 값에 해당하는 횟수 출력

 

결과

---

DP 개념은 알겠는데 코드로 짜기엔 아직 무리인듯.... 머리속에서 생각한 방법인데 코드로 구현하기에는 아직 부족한 것 같다.