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

링크

백준 1463 1로만들기

dp문제이다. 이런 유형의 문제들도 계속 풀다보니 어떻게 풀어야 할지 감이 오는 것 같다.

x를 줄여가며 계산하지 않고 x를 1부터 역으로 계산해가며 풀었다.
memoization을 위한 dp에서 idx는 숫자를 의미하고 idx에 해당하는 값은 그 숫자까지 걸리는 최소단계이다.

먼저 dp를 1씩 증가하는 리스트로 초기화를 해준다(그냥 1씩 증가시켜서 목표까지 도달하는 경우)

그후 1부터 목표x까지 반복을 돌리며 2와 3의 공배수일 경우 [i//3] [i//2] 중 작은것을 취하고 + 1을 해준다.
2또는 3의 배수일 경우엔 해당 수로 나눈 값과 1더해서 갈수 있는 값중 작은 값을 취하고 +1을 해준다.
그 무엇도 아닐경우 이전값에 +1을 해준다.

그 후 출력할 때 0이아닌 1부터 연산했으므로 -1을 해주고 출력한다.

정답 코드

x = int(input())
dp = [i for i in range(x + 1)]

for i in range(1, x + 1):
    if i % 3 == 0 and i % 2 == 0:
        dp[i] = min(dp[i//3] + 1, dp[i//2] + 1)
    elif i % 3 == 0:
        dp[i] = min(dp[i//3] + 1, dp[i-1] + 1)
    elif i % 2 == 0:
        dp[i] = min(dp[i//2] + 1, dp[i-1] + 1)
    else:
        dp[i] = dp[i-1] + 1

print(dp[x] - 1)

알게된 것👨‍💻

• dp문제에 더 익숙해졌다!