https://www.acmicpc.net/problem/1463
1463번: 1로 만들기
첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.
www.acmicpc.net
문제 해결을 위한 과정
이 문제의 경우 전형적인 Dynamic programming 방식으로 풀 수 있는 문제입니다. 풀이 역시 정형화되어있기 때문에 쉽게 해결할 수 있습니다.
문제에서 정수 X에 사용할 수 있는 연산은 다음과 같이 3가지라고 합니다.
1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.
즉 이 문제는 먼저 문제에서 주어진 대로 10^6크기의 dp라는 리스트를 만든 후 INF로 초기화해줍니다. 그 후 dp[0], dp[1]은 0으로 재정의 해줍니다. (1로 만드는 것이므로 1은 이미 1이기 때문에 0번의 연산이 필요하므로) 그 후 반복문으로 차근차근 조회해나가면서 1을 빼는 방법, 2를 나누는 방법, 3을 나누는 방법의 필요한 최솟값을 구해주면 됩니다.
예시에서 보여준 10의 경우를 살펴보겠습니다. 즉 필요한 식은 다음과 같습니다.
min(dp[i-1]+1, dp[i//2]+1, dp[i//3]+1)
소스코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
n = int(input())
INF = int(1e9)
dp = [INF] * (1+n)
dp[0] = 0
dp[1] = 0
for i in range(2, n+1):
dp[i] = dp[i-1] + 1
if i % 2 == 0:
dp[i] = min(dp[i], dp[i//2] + 1)
if i % 3 == 0:
dp[i] = min(dp[i], dp[i//3] + 1)
print(dp[n])
|
cs |
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 알고리즘 1026: 보물(Python) (0) | 2022.01.03 |
|---|---|
| 백준 알고리즘 1010번: 다리 놓기 (Python) (0) | 2021.12.27 |
| 백준 알고리즘 13549: 숨바꼭질 3(Python) (0) | 2021.02.25 |
| 백준 알고리즘 1504: 특정한 최단 경로(Python) (0) | 2021.02.23 |
| 백준 알고리즘 1068: 트리(Python) (0) | 2021.02.21 |