파이썬 1로 만들기(백준 BOJ 1463)
2022, Sep 26
문제
정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.
- X가 3으로 나누어 떨어지면, 3으로 나눈다.
- X가 2로 나누어 떨어지면, 2로 나눈다.
- 1을 뺀다.
정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.
입력
첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.
출력
첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.
예제 입력 1
2
예제 출력 1
1
예제 입력 2
10
예제 출력 2
3
📝 풀어보기
📌 정수 n을 입력받는다. n+1만큼 0이 들어간 리스트 dp를 생성한다.
문제는 연산을 적절히 사용해서 1을 만드는 것이기 때문에 0과 1은 연산횟수가 없다. 그러므로 0과 1은 제외한 2부터 n+1까지 반복하면서 연산 횟수를 저장한다.
2와 3으로 나누어 떨어지지 않는 수는 무조건 1을 빼야하므로 연산횟수 1이 추가된다.
i % 3 == 0 인 경우 dp[i], dp[i//3]+1 중에서 최소값을 구한다.
i % 2 == 0 인 경우 dp[i], dp[i//2]+1 중에서 최소값을 구한다.
dp[i//3]+1, dp[i//2]+1 인 이유는 만약 9를 연산한다고 할 때 9를 3으로 나누면 3이 나오고, 3에 대한 연산을 1번 더 해야하기 때문에 dp[3] 에 +1을 하는것과 같기 때문이다.
# 연산 세 개를 적절히 사용해서 1을 만들려고 한다.
# 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다
# 1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
# 2. X가 2로 나누어 떨어지면, 2로 나눈다.
# 3. 1을 뺀다.
n = int(input()) # 10
dp = [0] * (n+1) # [0] * 11
# 0, 1 은 연산 횟수가 없다.
for i in range(2, n+1): # 2, 3, 4, 5, 6, 7, 8, 9, 10, 11
dp[i] = dp[i-1]+1 # 2와 3으로 나누어 떨어지지 않으면 1을 무조건 빼야한다.
# 그러므로 연산횟수 1회가 증가한다.
# dp[2] = min(dp[2]=1, dp[1]=1)
# dp[4] = min(dp[4]=2, dp[2]+1=2)
if i % 2 == 0: # 2, 4, 6, 8, 10 숫자의 연산
dp[i] = min(dp[i], dp[i//2]+1) # dp[4] = dp[4](0), dp[2] = 0 + 1
# dp[6] = dp[6](0), dp[3] = 0
if i % 3 == 0: # 3, 6, 9,
dp[i] = min(dp[i], dp[i//3]+1) # dp[3] = dp[3](0), dp[1]+1(1)
# 2, 3, 4, 6, 8, 9, 10
# 5, 7 = 1
print(dp[n])