백준1463. 1로 만들기 - Python, DP, DFS

 

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

 

 

 

 

 

코드 & 풀이

dp 방식

import sys

data = sys.stdin.read().splitlines()
N = int(data[0])

dp = [0] * (N + 1)  # dp[i]: i를 1로 만드는 최소 연산 횟수

for i in range(2, N + 1):
    dp[i] = dp[i - 1] + 1  # 1을 빼는 연산
    if i % 2 == 0:
        dp[i] = min(dp[i], dp[i // 2] + 1)
    if i % 3 == 0:
        dp[i] = min(dp[i], dp[i // 3] + 1)

print(dp[N])

 

이 문제의 카테고리인 DP로 푸는 방식입니다.

 

일단 1을 빼는 경우를 먼저 합니다.

dp[i] = dp[i - 1] + 1

 

그 후부터는 이제 2로 나눠지냐, 3으로 나눠지냐의 차이입니다.

 

예로, 2로 나눠질 경우

 

나누기 2한 위치에 있는 값의 + 1한 값과 이전 위치에서 + 1한 값 중 작은 값을

 

기록합니다.

 

예시로 i = 10

 

10이 1을 뺀 연산에서 왔을 수도 있음 : 9 => 10 : dp[9] + 1

 

10은 2로 나누어떨어짐 : 5 => 10 (2배) 

 

=> 역으로 보면 10 // 2 = 5 => dp[5] + 1

 

10은 3으로는 나누어떨어지지 않음 → 이 경로는 사용 불가

 

 

dfs 방식

import sys

# 입력 처리
data = sys.stdin.read().splitlines()
N = int(data.pop(0))

def make(x):
    memo = {}

    def dfs(n):
        if n < 2:
            return 0
        if n in memo:
            return memo[n]
        res = min(
            dfs(n // 2) + 1 + (n % 2),
            dfs(n // 3) + 1 + (n % 3)
        )
        memo[n] = res
        return res

    return dfs(x)

print(make(N))

 

 

 

 

 

 

다음에 또 봐요