[Python] 백준 알고리즘 1463번: 1로 만들기, DP문제

이번에 푸는 문제는 백준 알고리즘 1463번 : 1로 만들기로 난이도는 Siver 3 에 해당한다.

문제는 다음과 같다.

 

이문제는 N이 주어졌을때 3가지 연산을 최소한으로 써서 1을 만드는게 목적이다.

 

10을 예로들면

10 -> 9 -> 3 -> 1

이렇게하면 3번의 연산을 하면 된다.

 

이문제도 메모이제이션이 필수이다. 그리고 어디로 연산을하는 것이 최소의 연산횟수인지를 추적하면 된다.

 

12을 예로 들면

1) 12 - 1 = 11

2) 12 / 3 = 4

3) 12 / 2 = 6

와 같이 3가지의 연산을 할 수 있다. 그렇다면 우리가 11, 4, 6 이 몇번의 연산을 필요로하는지 안다면 그중 가장 연산횟수에 +1이 12의 최소 연산횟수 일 것이다.

 

이것을 메모이제이션하면서 1부터 올라가면 아래 코드와 같다.

 

# 2020-07-18
# 2020-12-29 review
# 알고리즘 - DP
# 문제번호 : 1463

# 메모이제이션

testNum = int(input())

dp = []
dp.append(0)
def Devidedp(testNum):
    if(testNum == 1):
        #print(1)
        dp.append(0)
    elif(testNum == 2):
        #print(1)
        dp.append(1)
    elif(testNum == 3):
        dp.append(1)
    else:
        if(testNum%3 == 0 and testNum%2 == 0):
            dp.append(min(dp[testNum-1],dp[int(testNum/2)],dp[int(testNum/3)])+1)
        elif(testNum%3 == 0):
            dp.append(min(dp[testNum-1],dp[int(testNum/3)])+1)
        elif(testNum%2 == 0):
            dp.append(min(dp[testNum-1],dp[int(testNum/2)])+1)
        else:
            dp.append(dp[testNum-1]+1)

for i in range(1,testNum+1):
    Devidedp(i)
    #print(str(i), " ", str(dp[i]))
    #print(dp[testNum+1])

print(dp[testNum])

 

이것을 재귀를 사용하게 되면

# 2020-07-18
# 2020-12-29 review
# 알고리즘 - DP
# 문제번호 : 1463

# 메모이제이션

testNum = int(input())

dp = {}
dp[1] = 0

def Devidedp(testNum):
    if testNum in dp:
        return dp[testNum]
        
    if(testNum%3 == 0 and testNum%2 == 0):
        dp[testNum] = min(Devidedp(testNum//2),Devidedp(testNum//3))+1
        
    elif(testNum%3 == 0):
        dp[testNum] = min(Devidedp(testNum-1),Devidedp(testNum//3))+1
        
    elif(testNum%2 == 0):
        dp[testNum] = min(Devidedp(testNum-1),Devidedp(testNum//2))+1
        
    else:
        dp[testNum] = Devidedp(testNum-1)+1
    return dp[testNum]



print(Devidedp(testNum))

아래 것으로 하면 시간이 확 줄어드는 것을 볼 수 있다.

---

문제는 아래 ↓링크 ↓

1463번: 1로 만들기