백준 1463번 - 1로 만들기

[1로 만들기 ]

---

문제

 

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

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

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

 

각각의 연산을 순서대로 조건 1, 조건 2, 조건 3이라 하겠음.

---

입력

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

출력

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

---

예제 입력 1

2

 

예제 출력 1

1

---

예제 입력 2

10

 

예제 출력 2

3

---

[ 설명 ]

 

이 문제는 DP에 관련된 문제인데, DP는 다이내믹 프로그래밍 방법으로 푸는데, 다이나믹 프로그래밍 방법이라는 게 잘 모르겠다면 간단한 게 점화식을 찾아서 점화 식에 따라 리스트든 스택이든 자료형에 입력한 다음, 필요할 때 꺼내서 쓰는 방법입니다. 말로는 이해가 안 갈 텐데 차차 설명하면서 따라가면 이해가 될 것!!

 

입력되는 X가 3이나 2로 나누어지면 우선 나누고, 안나눈어지면 1을 빼면서 결론적으로 1이 될 때의 최솟값을 구하는 문제있은데. 이 문제를 보시고 바로 if라든지 while이라든지의 조건문을 조건에 따라 풀려고 했다면 조금 힘듭니다. 왜냐면 최솟값이라는 게 if문으로는 조금 까다롭거든요.

 

그럼 앞서 말했듯이 점화식을 찾아보도록 해봅시다.

(수학에서의 점화식과는 조금 개념이 다릅니다.)

 

시작해봅시다!

 

0 일 때 : 불가능하지만 편의상 0번 이라고 설정. ( 모든 자료형은 인덱스가 0부터 시작하기 때문에)

 

1 일때 : 1 그대로 출력 -> 0번

 

2 일 때 : 2 - 1(조건3) -> 1번

 

3 일때 : 3 // 3 (조건 1) -> 1번 ## 그런데 이런 식으로 가능합니다. 3 - 1(조건 3) = 2 // 2(조건 2) = 1 -> 2번

 

if문으로 간단하게 조건에 따라 계산하게 되면 여기서 문제가 발생합니다. 여러 번 계산하게 되면서 시간을 오래 소모하게 되고 코딩도 복잡해질 것입니다.

 

4 일 때 : 4 // 2(조건 2) = 2 //(조건 2) -> 2번  ## 4 - 1(조건 3) = 3 // 3(조건 1) = 1 -> 2번

n 일 때 :.....

.... 쭉쭉 계산될 것입니다.

앞서 말했듯 점화식을 찾으라는 것인데 이 연산을 하면서 무슨 규칙에 따라 계산하는 것 같은가요?

 

그건 바로, 

x가 3으로 나누어 떨이 지면 우선 나누고, 안되면 2로 나누어 떨어지는지 확인 그것도 안되면 마지막 -1 하는 식으로 순차적으로 계산을 이어갑니다.

우리는 이런 형태를 점화식 꼴로 표현해주면 되는 것입니다. (수학처럼 규칙 자체를 찾는 것이 아닌데, 찾으시면 다이내믹을 안 쓰고 이문제를 푸실 수 도 있죠..ㅎㅎ)

 

그림으로 설명하겠습니다.

 

점화식 찾는 과정

이런 식으로 점화식을 찾으면 파이썬 코딩로해주면 됩니다.

 

[ 코딩 ]

 

import sys

numbers = int(sys.stdin.readline())


dp = [0, 0, 1, 1]

for i in range(4, numbers + 1):
dp.append(dp [i - 1] + 1)

if i % 3 == 0:
dp [i] = min(dp [i], dp [i // 3] + 1)


if i % 2 == 0:
dp [i] = min(dp [i], dp [i // 2] + 1)

print(dp[numbers])

 

이런 식으로 하면 원하는 결과가 출력됩니다.

---

후기

 

생각보다 설명하는 게 만만치 않게 힘든데, 나를 가르치는 사람으로서 복습하는 겸

설명해보니 설명을 하면서도 문제에 대한 이해가 한층 더 커지는 거 같다.