[백준]1463번 1로 만들기 - DP

 

n = int(input())

dp = [0] * (n + 1)
for i in range(2, n + 1):
    dp[i] = dp[i - 1] + 1  # 1로 구하는 경우.

    if i % 3 == 0:  # 3으로 구하는 경우.
        dp[i] = min(dp[i], dp[i // 3] + 1)
    if i % 2 == 0:  # 2로 구하는 경우.
        dp[i] = min(dp[i], dp[i // 2] + 1)
print(dp[-1])

 

코드 설명 

n+1 만큼의 길이를 가진 dp 리스트를 생성함으로써 index 를 문제와 맞춰준다.(0 인덱스 사용 X)

값이 1을 입력 받는 경우에는 연산의 횟수가 0 이므로 반복문을 수행하지 않고 그냥 출력하게 한다.

값이 2이상인 경우에는 2 부터 n 까지 반복을 진행한다.

1을 빼는 경우를 이용하는 것이 가장 많은 연산의 횟수를 가진다. 따라서 처음에 모두 1을 빼면서 구한다고 생각을 하여 준다.

만약 3 이나 2 로 나눌수 있다면 dp[i] 에 저장된 값과 dp[i //3 ] + 1 만큼의 값중 작은것으로 dp 리스트를 갱신하여 준다.

 

Point : 기본적으로 1을 빼는 연산의 횟수로 모두 설정하여 준다. 만약 2와 3으로 나누는 연산이 가능하다면 dp[i]의 값과 i//3에 저장된 값 + 1 을 비교하여 준다. i // 2or3 의 인덱스에 값이 저장되어 있기 때문이다.