[백준] 1463 : 1로 만들기 (파이썬 / Python)

1로 만들기

https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

---

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

예제 입력 1

2

예제 출력 1

1

예제 입력 2

10

예제 출력 2

3

힌트

10의 경우에 10 → 9 → 3 → 1 로 3번 만에 만들 수 있다.

---

코드

n = int(input())
d = [0] * (10**6+1) # 연산을 사용하는 횟수의 최솟값 저장

for i in range(2, n+1):
   d[i] = d[i-1] + 1 # 1을 빼는 연산
   if i % 3 == 0: # 3을 나누는 연산
      d[i] = min(d[i], d[i // 3] + 1)
   if i % 2 == 0: # 2를 나누는 연산
      d[i] = min(d[i], d[i // 2] + 1)
      
print(d[n])

풀이

이 문제는 동적계획법의 bottom-up 방식으로 풀이할 수 있다. 그 이유는 메모이제이션 방법을 사용해 중복해 계산되는 값을 저장하여 효율을 높여주고, 초기값을 알기 때문이다.

우선 연산을 사용하는 횟수의 최솟값을 저장하기 위해 d라는 배열을 생성(ex. 1의 값을 인덱스 1의 위치에 저장)해주고, 그 값은 0으로 초기화시킨다. d[1] = 0인 이유는 1이면 연산을 하지 않아도 되기 때문이다. 

이 문제에서 중요한 점은 힌트에서 볼 수 있는데 10의 경우 10 -> 9 -> 3 -> 1로 3번의 연산을 사용하는 것이 최솟값인데 첫 번째 연산에서 10의 경우 2로 나누어떨어지기 때문에 고려할 연산이 여러 개이다. 따라서, (1) 3으로 나누는 연산, (2) 2로 나누는 연산, (3) 1을 빼는 연산을 모두 고려하여 연산을 사용하는 횟수의 최솟값(min)을 출력해야 하는 것이다.

for문의 1번째 line을 보면 d[i] = d[i-1] + 1으로 구현되어 있는데, 이는 1을 빼는 연산을 의미한다. 쉽게 말하자면 d[i-1] (-> i-1의 연산을 사용하는 횟수의 최솟값)에 1만을 더해 1을 빼는 연산을 수행한다는 것이다. 조금 더 풀어 설명하자면 i에서 1을 뺀 후, i-1에서 수행한 최소 연산을 수행하는 것이다. 우선 이 값을 d[i]에 저장해두고 (1) 3으로 나누는 연산, (2) 2로 나누는 연산이 가능한 지 본 후, 어떤 경우가 연산 횟수의 최솟값인지 살펴볼 것이다.

for문의 2번째 line을 보면 i가 3으로 나누어 떨어질 경우, d[i]와 d[i // 3] + 1 중 최솟값을 연산 횟수로 선택하겠다는 것이다. 이 때 d[i]는 for문의 1번째 line에서 구한 1을 뺀 연산이며, d[i // 3] + 1은 3을 나누는 연산을 의미한다. (위에서 본 것과 같이) 쉽게 말하자면 d[i // 3] (-> i // 3의 연산을 사용하는 횟수의 최솟값)에 1만을 더해 3을 나누는 연산을 수행한다는 것이다. 조금 더 풀어 설명하자면 i에서 3을 나눈 후, i // 3에서 수행한 최소 연산을 수행하는 것이다.

for문의 3번째 line의 경우도, for문의 2번째 line의 경우와 같다.