[python] 백준 1463번 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이 주어진다.

출력

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

 

 

 

 

 

---

 

 

 

 

💻 코드

 

 

 

import sys

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

d = [0] * 1000001

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])

 

 

 

 

 

 

 

📝 풀이

 

 

이 문제는 처음에 당연히 if else문을 사용해서 3으로 나누어 떨어지면 나누고, 2로 나누어 떨어지면 2로 나누면 2로 나누고, 둘 다 안되면 -1을 하는 식으로 푸면 되는 줄 알았다. 예제 입력이었던 10까지도 처리해서 해보았다. 그런데 틀렸다고 나왔었다. 알고 보니 내가 푼 방식은 그리디 알고리즘으로 푼 것이었고, 이 알고리즘으로 풀면 처리가 안되는 예외 숫자들이 많았다. 16, 40, 642 등등... 그리디 알고리즘으로는 풀리지 않는 문제였다.

 

 

이 문제는 다이나믹 프로그래밍 문제였다. 다이나믹 프로그래밍의 조건인 최적 부분 구조이면서 중복되는 부분 문제가 있었다. 

 

 

1부터 차례대로 연산을 해보면,

 

 

입력 1

출력 0

---

입력 2

2 // 2 = 1

출력 1

---

입력 3

3 // 3 = 1

출력 1

---

입력 4

4 // 2 = 2

2 // 2 = 1

출력 2

---

입력 5

5 - 1 = 4

4 // 2 = 2

2 // 2 = 1

출력 3

---

입력 6

6 // 3 = 2

2 // 2 = 1

출력 2

 

 

 

이와 같이 나온다. 여기에서 주황색 부분끼리 연산이 겹치고, 초록색 부분끼리 연산을 겹친다. n이 4일 때 4를 2로 나누면 2가 나오는데 2는 n이 2일 때 계산과 동일하므로 연산이 중복됨을 볼 수 있다. 따라서 이는 다이나믹 프로그래밍으로 풀어야하는 문제인 것이다.

 

 

다이나믹 프로그래밍 문제는 TopDown 방식과 BottomUp 방식, 2가지 방식으로 풀 수 있는데 BottomUp 방식으로 풀었다. 

 

먼저 한 번 계산한 결과는 메모리 공간에 저장해둘 수 있도록 배열 d를 만들고 최대 입력인 1000000의 개수 + 1만큼 공간을 만들었다. 그리고 연산하는데 1은 연산이 필요없으므로 2부터 n + 1까지 for문을 돌렸다. 이제 어떻게 연산을 하였을 때 1이 만들어지는 횟수가 최소가 되는지 연산을 해야하는데, 어떤 것이 최소가 될 지 모르므로 elif로 작성하면 안되고 모두 if로 작성해야한다. 먼저 1을 뺄 경우 횟수를 1번 추가해주어야하므로 d[i] = d[i - 1] + 1을 해준다. 그리고 if문을 이용하여 3으로 나누어 떨어지는 경우와 2로 나누어 떨어지는 경우 횟수를 1번 추가해준 뒤에 1을 뺀 경우와 비교하여 최솟값을 넣어주는 방식으로 연산을 반복하여 결과값을 도출해내었다.

 

 

 

 

 

 

 

---

 

 

 

 

아직 코드를 완벽하게 이해하고 작성하지는 못한 것 같아서 다이나믹 프로그래밍 문제를 더 풀어 보면서 이해를 해봐야 겠다고 생각했다...

 

 

 

 

 

💡 다이나믹 프로그래밍 개념

 

 

2022.06.22 - [Algorithm 개념 정리] - 다이나믹 프로그래밍 Dynamic Programming

다이나믹 프로그래밍 Dynamic Programming

 

 

 

 

※ 참고한 글

 

 

 

https://www.acmicpc.net/board/view/89063

글 읽기 - 그리디는 왜 안되나요?

 

 

https://seongonion.tistory.com/40

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