[알고리즘] 백준 1463번 문제풀이

date

Sep 4, 2023

slug

baekjoon-1463

author

status

Public

백준 1463 파이썬


n=int(input())

dp=[0]*(n+1)

for i in range(2, n+1):
    # 1을 빼는 방법-> 이전 계산 결과에 1 더하는 방법. 왜냐면 -1을 한번만 하기 때문에.
    dp[i]=dp[i-1]+1

    # 3으로 나누는 방법
    if i%3==0:
        dp[i]=min(dp[i], dp[i//3]+1)
    # 2로 나누는 방법
    if i%2==0:
        dp[i]=min(dp[i], dp[i//2]+1)

print(dp[n])

1을 빼는 방법의 코드 동작:

1을 뺀, 바로 이전 값의 방법 수에서 1을 더함.

(ex 3이면, 2의 횟수에서 -1을 한번 했으니까 2에서 계산 결과에 -1을 한번 한 것으로 둠.)

3을 나누는 방법의 코드 동작:

만약, 3로 나누어 떨어진다면,

-1을 뺀 이전 방법 수와 현재 3로 나누는 방법 수 중에 적은 방법 수를 dp[i]로 둔다.

2로 나누는 방법의 코드 동작:

만약, 2로 나누어 떨어진다면,

-1을 뺀 이전 방법 수와 현재 2로 나누는 방법 수 중에 적은 방법 수를 dp[i]로 둔다.