[Python][백준] 백준 1463번 1로 만들기 풀이 | DP와 Divide and conquer

DP(Dynamic Programming)

큰 문제를 작은 문제로 나누어 푸는 알고리즘이다.

Divide and conquer와는 다르다!

Divide and conquer는 큰 문제를 작은 단위로 나누어 해결한 다음 합치는 알고리즘이다. (예시 merge sort)

 

오늘은 DP를 이용하여 푸는 백준 1463번의 코드를 공유하겠다.

# DP를 이용한 풀이
n = int(input())
dp = [0] * max(4, n+1)
dp[2], dp[3] = 1, 1
for i in range(4, n+1):
    temp1 = dp[i//3] if i % 3 == 0 else float("inf")
    temp2 = dp[i//2] if i % 2 == 0 else float("inf")
    
    dp[i] = min(temp1, temp2, dp[i-1]) + 1

print(dp[n])

 

 

 

앞으로 DP 문제 많이 풀 예정.

 

---

원래 이 문제를 풀때 다른 방법으로 시도하려 했다.

# 인수분해 트리 만들기

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.center = None  # 2 나누기
        self.right = None  # 1 빼기

    def __str__(self):
        return str(self.data)


class Tree:
    def __init__(self):
        self.root = None

    def makeRoot(self, node, left_node, center_node, right_node):
        if self.root is None:
            self.root = node
        node.left = left_node
        node.center = center_node
        node.right = right_node

    def getHeight(self, root):
        if root is None:
            return -1
        left_height = self.getHeight(root.left) + 1
        center_height = self.getHeight(root.center) + 1
        right_height = self.getHeight(root.right) + 1

        return max(left_height, center_height, right_height)

    def find1(self):


def P1463():
    num = int(input())
    n = Node(num)
    t = Tree()
    while True:
        temp = num
        if temp == 1:
            return
        if num % 3 == 0:
            left = Node(num / 3)
        else:
            left = None

        if num % 2 == 0:
            center = Node(num / 2)
        else:
            center = None
        right = Node(num-1)

        t.makeRoot(n, left, center, right)

if __name__ == '__main__':
    P1463()

한 눈에 봐도 복잡하지 않은가? 트리 구조를 이용하여 모든 경우의 수를 찾으려고 했다. 그러나, 이 알고리즘은 완성하지도 못했을 뿐더러, 만약에 코드를 구현한다 해도, 시간초과되었을 것이다.