문제
정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.
- X가 3으로 나누어 떨어지면, 3으로 나눈다.
- X가 2로 나누어 떨어지면, 2로 나눈다.
- 1을 뺀다.
정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.
입력
첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.
출력
첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.
과정
처음에는 ‘1을 빼기보다 나누는 게 숫자가 더 작아지니까 2나 3으로 나눠지는 경우엔 무조건 나누면 되지 않을까?’하는 생각을 했는데 예제를 보자마자 바로 아니라는 것을 깨달았다.
DP 문제는 우선 1부터 10까지의 답을 적어나가다 보면 패턴을 쉽게 발견할 수 있는 것 같다. 그래서 우선 1부터 10까지 답을 써봤다.
| 입력 | 출력 |
|---|---|
| 1 | 0 |
| 2 | 1 |
| 3 | 1 |
| 4 | 2 |
| 5 | 3 |
| 6 | 2 |
| 7 | 3 |
| 8 | 3 |
| 9 | 2 |
| 10 | 3 |
여기서 찾은 패턴을 10을 예로 들어 설명하겠다.
우리는 숫자를 2로 나누거나, 3으로 나누거나, 1을 뺄 수 있다. 10의 경우 3으로는 나눠지지 않으므로 경우의 수는 2로 나누거나 1을 빼는 것으로 나뉜다.
- 2로 나누는 경우 10을 2로 나누면 5가 되고, 5는 1이 되려면 3회의 연산이 필요하므로 총 4회의 연산이 필요하다.
- 1을 빼는 경우 10에서 1을 빼면 9가 되고 9는 1이 되려면 2회의 연산이 필요하므로 총 3회의 연산이 필요하다.
따라서 10의 경우에 필요한 연산은 3회가 되는 것이다.
결과적으로 숫자를 2로 나누었을 때, 3으로 나누었을 때, 1을 뺐을 때의 연산 횟수 중 가장 작은 경우를 선택해 1을 더하면 답을 구할 수 있는 것이다.
이것을 아래와 같이 구현하였다.
X = int(input())
list = [0]*(X+1)
list[1] = 0
for i in range (2, X+1):
if i%2 == 0 :
list[i] = min(list[i-1], list[i//2])+1
if i%3 == 0 :
list[i] = min(list[i-1], list[i//3])+1
if i%2 != 0 and i%3 != 0 :
list[i] = list[i-1]+1
print(list[X])하지만 결과는 !?!? 실패 ^^ ㅜ
최종 코드
도대체 뭐가 잘못되었는지 확인해보니 2와 3으로 모두 나눠질 때 3가지 경우 중에서 가장 작은 것으로 선택이 되어야 하는데 이 과정이 제대로 이루어 지지 않았다. 셋 중에 list[i//2]가 가장 작은 경우에 답이 달랐다. 따라서 인터넷을 참고하여 아래와 같이 코드를 완성했다.
X = int(input())
list = [0]*(X+1)
list[1] = 0
for i in range (2, X+1):
list[i] = list[i-1]+1
if i%2 == 0 :
list[i] = min(list[i], list[i//2]+1)
if i%3 == 0 :
list[i] = min(list[i], list[i//3]+1)
print(list[X])우선 list[i]를 list[i-1]+1로 두고, list[i]와 list[i//2]+1, list[i]와 list[i//3]+1을 비교하는 것으로 바꾸니 정상적으로 답이 출력되었다.
문제에 대한 접근은 잘 했는데 구현에서 좀 삐끗한 것 같다. 더 꼼꼼하게 구현하자!