1로 만들기

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번 만에 만들 수 있다.

알고리즘 분류

• 다이나믹 프로그래밍

💯 문제 풀이

💡 문제 이해

숫자가 주어진다. 그때 아래 연산중에 하나를 해서 1로 만들어야한다. 1로 가는 가장 빠른 방법의 연산횟수를 출력해주면된다.

🔓 문제 접근 과정

HS형의 도움을 받아 이 문제를 잘 이해할 수 있었다.(Thanks to HS🙇🏻‍♂️)

먼저 처음 이 문제를 접할때 어떤 생각을 하면 되냐면

어떤 수이던 1을 계속 빼면 1로 갈수있다.
그런데 3을 나눌수있거나 2로 나눌수있다면 연산횟수가 줄어드는것이다.

이 생각을 하면 좋다.
그래서 점화식은 다음과 같다.

i의 연산 횟수 = i-1의 연산횟수 + 1

그런데 3으로 나누어 떨어지는 경우와 2로 나누어 떨어지는 경우를 생각해보자.

예를 들어 6이라고 하면 6은 3으로 나누어 떨어지므로 바로 2로 갈수있다. 그 후에 2의 연산횟수를 더해주어야 한다. 즉, 3으로 나눈 연산횟수 1번 + 기존에 계산했던 2의 연산횟수를 해주면 된다.

그래서 dp를 사용하는것이다. dp를 사용해서 1부터 주어진 수까지 각각의 연산 횟수가 들어간다. 그래서 3으로 나누어 떨어지거나 2로 나누어떨어지고 남은 나머지의 연산횟수를 추가로 계산할 필요 없이 dp에서 꺼내주기만 하면 된다.

🔑 최종 코드

from sys import stdin

input = stdin.readline

num = int(input())

dp = [0] * (num+1)

for i in range(2, num+1):
    dp[0] = 0
    dp[1] = 0
    dp[i] = dp[i-1] +1

    if i % 3 == 0 and dp[i] > dp[i//3]+1:
        dp[i] = dp[i//3] +1
    if i % 2 == 0 and dp[i] > dp[i//2]+1:
        dp[i] = dp[i//2] +1

print(dp[num])

🙋‍♂️ 오늘의 TMI

결국 아이패드 프로를 샀다.

잘 산건지 모르겠다…. 🤔