[백준] 1463. 1로만들기 Python

문제 링크 : 1463.1로만들기

1463번: 1로 만들기

풀이 코드 : GIthub

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

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

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

 

풀이

 

다음과 같은 접근으로 생각했다.

 

1. 3으로 나눌수록 빠르게 1에 도달할 수 있으니 3으로 나눔

2. 3으로 나눌 수 없다면 2로 나눔

3. 3, 2로 나눌 수 없다면 1을 뺌

 

코드로 구현하면 아래와 같다.

count = 0
i = int(input())
while True:
    if i == 1:
        print(count)
        break
    else:
        if i % 3 == 0:
            i = i // 3
            count += 1
        elif (i-1) % 3 == 0:
            i -= 1 
            i = i // 3
            count += 2
        elif i % 2 == 0:
            i = i // 2
            count += 1
        else:
            i -= 1 
            count += 1
count = 0

 

그러나 문제가 하나 있었는데...

3으로 나눈다고해서 무조건적으로 빠르게 1에 도달할 수 있는게 아니였다.

 

https://www.acmicpc.net/board/view/123717 이 링크에서 풀이과정을 참고하여 풀었다.

 

x=int(input())
dp = [-1] * 1000001
dp[1] = 0
def rec(n):
    if -1 != dp[n]:
        return dp[n]
    if (n%3==0) and (n%2==0):
        dp[n]=min(rec(n//3)+1, rec(n//2)+1)
    elif n%3==0:
        dp[n]=min(rec(n//3)+1, rec(n-1)+1)
    elif n%2==0:
        dp[n]=min(rec(n//2)+1, rec(n-1)+1)
    else:
        dp[n]=rec(n-1)+1
    return dp[n]
print(rec(x))

 

 

풀이과정은 DFS와 DP를 이용한 Bottom-Up 방식이였다.

 

코드의 조건은 다음과 같다.

1. 3 그리고 2로 나누어 떨어진다면 

2. 3으로 나누어 떨어진다면

3. 2로 나누어 떨어진다면

4. 1을 뺀다.

 

 

특히 2, 3번을 만족하더라도 1을 그냥 뺐을 때와 또 비교하여 최소값을 찾는게 관건이였다.

만약 10을 1로 만들 때 최소 연산을 구한다고 하면

 

위 그림과 같이 DP List가 있을 것이다(각 값은 해당 값이 1이 되는데 필요한 연산 횟수)

여기서 1은 연산이 0번 필요함을 알고 있음으로 0의 값을 준다. 

그리고 10은 3번 조건을 만족함으로 5 그리고 9로 나누어 질 수 있다.

 

5는 또 4번을 만족하므로 4가 된다.

 

4는 3번을 만족함으로 2와3으로 나누어진다.

 

2는 또 3번을 만족한다. 1과 1로 나누어진다. 

 

우리는 1이 0번 연산이 필요하다는 것을 알고있다. 그러므로 이제 위로 올라간다. 위로 올라갈때는 +1 하여 올라간다.(연산 1회 추가)

 

1을 DP 2번 자리에 추가한다.

같은 방식으로 계속 진행하다보면 5를 1로 만드는데에는 3번의 연산이 필요하다는것을 알게된다.

 

같은 방식으로 오른쪽 9 부분도 진행한다.

왼쪽 부분을 진행하면서 DP에 값이 많이 저장되어있기 때문에 1이 될때까지 내려갈 필요는 없다. 

9가 1이 되는데는 2번이면 된다.

 

5가 1이되는데는 3번, 9가 1이되는데는 2번이 필요하므로 9를 취하여 올라간다. 

 

그러면 최종 답은 3이 된다.