[백준 1463] 1로 만들기

 

 

문제

---

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

1463번: 1로 만들기

 

 

나의 풀이

---

DP를 사용해 쉽게 풀 수 있는 문제이다. input으로 주어진 각 수는 아래의 연산 중 한 가지를 할 수 있다.

• 2로 나누어 떨어지면 2로 나눈다.
• 3으로 나누어 떨어지면 3으로 나눈다.
• 1을 뺀다.

이를 반복해서 결과적으로 1이란 수를 만들어야 하는데, 이를 DP의 점화식과 연관지어 생각해보면 쉽다. 만약 내가 10이란 수를 input으로 받는다고 가정해보자.

1. 10->5->4->2->1
2. 10->9->3->1
3. 10->9->8->7->...->1

위의 경우 말고도 10을 1로 만들기 위해선 굉장히 다양한 경우가 존재한다. 이 중 우리는 연산을 최소화하는 경우를 return해야 한다. dp라는 배열을 만들고, dp[i]에 i를 1로 만들기 위한 최소 연산의 수를 저장하자. 그럼 dp[10]=min(dp[10//2], dp[10-1]) + 1이 된다. 만약 2와 3의 공배수인 6이라면 dp[6]=min(dp[6-1], min(dp[6//2],dp[6//3]))이 된다. 이처럼 bottom-up 방식으로 쌓아나가 해당 수의 dp[x]를 구하게 되면 끝이 난다.

 

코드

---

x = int(input())
dp = [0] * (10**6 + 1)
dp[1], dp[2], dp[3] = 0, 1, 1
if x==1:
    print(0)
elif x==2 or x==3:
    print(1)
else:
    for i in range(4,x+1):
        if i%2==0 and i%3==0:
            dp[i] = min(dp[i-1], min(dp[i//2], dp[i//3])) + 1
        elif i%2==0:
            dp[i] = min(dp[i-1], dp[i//2]) + 1
        elif i%3==0:
            dp[i] = min(dp[i-1], dp[i//3]) + 1
        else:
            dp[i] = dp[i-1] + 1
    print(dp[x])