[백준] 1로 만들기-I am yumida

문제는 아래와 같습니다.

 

https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

 

풀이과정

 

10을 1로 만드는 과정의 최소 횟수를 구하면서 풀이를 해보겠습니다.

우선 다이나믹 프로그래밍의 상향식(Bottom up) 방법으로 구했습니다.

 

풀이과정의 아이디어를 표현하면 아래와 같습니다.

괄호([])안에 있는 내용은 숫자가 1이 되기까지의 과정을 나열한 것입니다. 

 

1을 1로 만드는 과정의 최소 횟수: 0

2를 1로 만드는 과정의 최소 횟수: 1 [2를 2로 나눈 몫: 1]

3을 1로 만드는 과정의 최소 횟수: 1 [3을 3으로 나눈 몫: 1]

4를 1로 만드는 과정의 최소 횟수: 2 [4를 2로 나눈 몫: 2 -> 2를 2로 나눈 몫: 1]

5를 1로 만드는 과정의 최소 횟수: 3 [5를 1로 뺀 값: 4 -> 4를 2로 나눈 몫: 2 -> 2를 2로 나눈 몫: 1]

6을 1로 만드는 과정의 최소 횟수: 2 [6을 3으로 나눈 몫: 2 -> 2를 2로 나눈 몫: 1]

7을 1로 만드는 과정의 최소 횟수: 3 [7을 1로 뺀 값: 6 -> 6을 3으로 나눈 몫: 2 -> 2를 2로 나눈 몫: 1]

8을 1로 만드는 과정의 최소 횟수: 3 [8을 2로 나눈 몫: 4 -> 4를 2로 나눈 몫: 2 -> 2를 2로 나눈 몫: 1]

9를 1로 만드는 과정의 최소 횟수: 2 [9를 3으로 나눈 몫: 3 -> 3을 3으로 나눈 몫: 1]

10을 1로 만드는 과정의 최소 횟수: 3 [10을 1로 뺸 값: 9 -> 9를 3으로 나눈 몫: 3 -> 3을 3으로 나눈 몫: 1]

 

1을 1로 만드는 최소 과정부터 10을 1로 만드는 최소 과정을 살펴보면, 겹치는 계산이 있는 것을 알 수 있습니다.

 

예를 들면, 10을 1로 만드는 최소 과정에서 10을 1로 뺀 값인 9를 1로 만드는 과정이 앞에서 9를 1로 만드는 최소 과정과 같은 것을 알 수 있습니다.

또한 8을 1로 만드는 최소 과정에서 8을 2로 나눈 값인 4를 1로 만드는 과정이 앞에서 4를 1로 만드는 최소 과정과 같은 것을 알 수 있습니다.

 

이렇게 겹치는 계산을 반영해 10의 최소 횟수를 구했습니다. 

코드를 먼저 제시하고, 구현 과정의 일부를 보여드리겠습니다.[설명은 더보기에 있습니다.]

N = 10
dp = [0,0,1,1]

for i in range(4,10+1):
    dp.append(dp[i-1]+1)
    if i%2 == 0:    dp[i] = min(dp[i//2]+1, dp[i])
    if i%3 == 0:    dp[i] = min(dp[i//3]+1, dp[i])
  
print(dp)
>>> [0, 0, 1, 1, 2, 3, 2, 3, 3, 2, 3]

1) i = 4 일때

N = 10
dp = [0,0,1,1]

• dp의 0번째 원소: 인덱스를 맞춰주기 위한 값
• 1번째 원소: 1에서 1이 되기까지의 최소 횟수
• 2번째 원소: 2에서 1이 되기까지의 최소 횟수
• 3번째 원소: 3에서 1이 되기까지의 최소 횟수

i=4
dp.append(dp[i-1]+1) #dp=[0,0,1,1,2]
if i%2 == 0:    dp[i] = min(dp[i//2]+1, dp[i])

• dp에서 dp[4]=min(dp[2]+1,dp[4]): dp[2]+1 은 2에서 1이 되기까지의 최소 횟수에 1회 더한 값입니다.
• 즉, 4에서 1이 되기 위해 2에서 1이 되기까지의 최소 과정에서 4에서 2로 나누는 과정을 추가했습니다.
• dp[4]는 이전 과정 dp[3]에 1회 더한 값입니다.
• dp[2]+1과 dp[4]를 비교해 최소값을 dp[4]에 할당합니다.
• 할당된 dp[4]는 4에서 1이 되기까지의 최소 횟수입니다.

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

2) i = 5 일때

N = 10
dp = [0,0,1,1,2]

• dp의 0번째 원소: 인덱스를 맞춰주기 위한 값
• 1번째 원소: 1에서 1이 되기까지의 최소 횟수
• 2번째 원소: 2에서 1이 되기까지의 최소 횟수
• 3번째 원소: 3에서 1이 되기까지의 최소 횟수
• 4번째 원소: 4에서 1이 되기까지의 최소 횟수

i=5
dp.append(dp[i-1]+1) #dp=[0,0,1,1,2,3]
if i%2 == 0:    dp[i] = min(dp[i//2]+1, dp[i]) 
if i%3 == 0:    dp[i] = min(dp[i//3]+1, dp[i])

• dp에서 dp[5]는 dp[4]+1 로, 4에서 1이 되기까지의 최소 횟수에 1회 더한 값입니다.
• 5는 2로 나누어 떨어지지 않고 3으로도 나누어 떨어지지 않습니다.
• 따라서 1을 빼는 과정을 dp[4]에 추가합니다
• 계산된 dp[5]는 5에서 1이 되기까지의 최소 횟수입니다.

print(dp)
>>> [0, 0, 1, 1, 2, 3]

3) i = 6 일때

N = 10
dp = [0,0,1,1,2,3]

• dp의 0번째 원소: 인덱스를 맞춰주기 위한 값
• 1번째 원소: 1에서 1이 되기까지의 최소 횟수
• 2번째 원소: 2에서 1이 되기까지의 최소 횟수
• 3번째 원소: 3에서 1이 되기까지의 최소 횟수
• 4번째 원소: 4에서 1이 되기까지의 최소 횟수
• 5번째 원소: 5에서 1이 되기까지의 최소 횟수

i=6
dp.append(dp[i-1]+1) #dp=[0,0,1,1,2,3,4]
if i%2 == 0:    dp[i] = min(dp[i//2]+1, dp[i])

 

• dp에서 dp[6]=min(dp[3]+1,dp[6]): dp[3]+1 은 3에서 1이 되기까지의 최소 횟수에 1회 더한 값입니다.
• 즉, 6에서 1이 되기 위해 3에서 1이 되기까지의 최소 과정에서 6에서 2로 나누는 과정을 추가했습니다.
• dp[6]는 이전 과정 dp[5]에 1회 더한 값입니다.
• dp[3]+1과 dp[6]를 비교해 최소값을 dp[6]에 할당합니다.
• 할당된 dp[6]는 6에서 1이 되기까지의 최소 횟수입니다.

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

 

코드

N = int(input())
dp = [0,0,1,1]

for i in range(4,N+1):
    dp.append(dp[i-1]+1)
    if i%2 == 0:    dp[i] = min(dp[i//2]+1, dp[i])
    if i%3 == 0:    dp[i] = min(dp[i//3]+1, dp[i])
  
print(dp[N])