[백준 BOJ_1463] 1로 만들기 Python 풀이

출처: 백준 온라인 저지

문제

풀이

동적계획법으로 풀어 보겠습니다.

cache는 index값으로 헷갈리지 않게 0부터 N+1까지 0으로 초기화된 list로 시작합니다.

N=1에는 아무런 연산을 하지 않아도 되기 때문에 0으로 초기화된 값을 딱히 건드리지 않아도 됩니다.

for loop을 2부터 N+1까지 돌려줍니다.

• cache[i] = cache[i//3] + 1
  • i가 3의 배수라면 i를 3으로 나눈 수의 최소 연산 수(cache[i//3])에 1을 더한 값을 저장해줍니다.
    • 3으로 나누면서 연산이 하나 늘어나기 때문입니다.
• 같은 맥락으로 i가 2의 배수일 때도 저장해주어야 하는데, i가 3과 2의 공배수일 수도 있기 때문에 elif가 아닌 if로 써주어야 합니다.
  • cache[i] = min(cache[i], cache[i//2] + 1)
    • 만약 cache[i]가 초기화된 값인 0이 아닐 경우, 현재 저장된 cache[i]값과, i를 2로 나눈 수의 최소 연산 수(cache[i//2])에 1을 더한 값 둘 중 더 작은 값으로 저장해줍니다.
  • cache[i] = cache[i//2] + 1
    • cache[i]가 0일 경우에는 그냥 i를 2로 나눈 수의 최소 연산 수(cache[i//2])에 1을 더한 값을 저장해줍니다.
• i가 3의 배수도, 2의 배수도 아니면 1을 빼줘야 하지만, 3과 2의 배수일 경우에도 1을 먼저 뺀 값이 더 적게 연산을 하게 될 수도 있어서 두 가지 경우 모두 고려해주기 위해 이번에도 elif가 아닌 if로 써주어야 합니다.
  • cache[i] = min(cache[i], cache[i-1] + 1)
    • cache[i]가 초기화된 값인 0이 아닐 경우, 현재 저장된 cache[i]값과, i에서 1을 뺀 수의 최소 연산 수(cache[i-1])에 1을 더한 값 둘 중 더 작은 값으로 저장해줍니다.
  • cache[i] = cache[i-1] + 1
    • cache[i]가 0일 경우에는 i에서 1을 뺀 수의 최소 연산 수(cache[i-1])에 1을 더한 값을 저장해줍니다.

cache[N]을 출력해줍니다.

코드

N = int(input())
cache = [0 for _ in range(N+1)]
if N > 1:
    for i in range(2, N+1):
        if i % 3 == 0:
            cache[i] = cache[i//3] + 1
        if i % 2 == 0:
            if cache[i]:
                cache[i] = min(cache[i], cache[i//2] + 1)
            else:
                cache[i] = cache[i//2] + 1
        if cache[i]:
            cache[i] = min(cache[i], cache[i-1] + 1)
        else:
            cache[i] = cache[i-1] + 1
print(cache[N])