[Python] 1463 - 1로 만들기

풀이

정수 N에 대하여, 세 가지의 연산을 적절히 활용하여 연산 사용 횟수를 최소화 시키는 문제이다.

10의 경우에 예로 들면, 10 -> 9 -> 3 -> 1로 연산 3회에 완료된다.

하지만 다른 경우로 생각한다면 10 -> 5 -> 4 -> 2 -> 1로 연산 4회로 생각할 수도 있다.

 

이 문제에서 핵심은 역추적이다. 어떤 수가 3개의 연산 중 하나를 통해 10이 된다라고 가정해 보면, 9 + 1 또는 5 x 2가 된다. 9와 5는 각각 2번, 3번의 연산을 통해 만들어진 수다. 그렇기에 둘 중 최솟값인 2에 연산 +1번을 하여 10의 최소 연산 횟수는 3이다.

 

이런식의 역추적 알고리즘을 코드로 작성해보면 다음과 같다.

# 1463 1로 만들기

n = int(input())

d = [0] * (n + 1) # 입력 수의 크기 리스트 생성
for i in range(2, n + 1):
    d[i] = d[i - 1] + 1 # 1을 뺀 경우
    if i % 3 == 0:
        d[i] = min(d[i], d[i // 3] + 1) # 3으로 나누었을 때와 1을 뺏을 때의 연산 횟수 비교
    if i % 2 == 0:
        d[i] = min(d[i], d[i // 2] + 1) # 2로 나누었을 때와 1을 뺏을 때의 연산 횟수 비교

print(d[n])

실제로 2 부터 10의 수 중 최소 연산 횟수는 다음과 같이 나온다