[Baekjoon] 1463번 : 1로 만들기(Python)

[Baekjoon] 1463번 : 1로 만들기(Python)

 

목차

 

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

1463번: 1로 만들기

Python

 

방법 1 - 메모리 39112KB / 시간 548ms / 코드 길이 261B

 

Buttom-Up 방식의 DP이며 Memorization으로 그 값을 도출할 수 있다.

특히 2로 나눠질 때 이전 단계를 통해 얻은 dp[i]의 값과 dp[i//2]+1 값 중 작은 값을 선택하도록 한다.

3으로 나눠질 때 역시 마찬가지이다.

 

x = int(input())
dp = [0 for _ in range(x+1)]
dp[1] = 0
for i in range(2, x+1):
    dp[i] = dp[i-1] + 1
    if not i % 2 and dp[i] > dp[i//2] + 1:
        dp[i] = dp[i//2] + 1
    if not i % 3 and dp[i] > dp[i//3] + 1:
        dp[i] = dp[i//3] + 1

print(dp[x])

 

방법 2 - 메모리 39108KB / 시간 660ms / 코드 길이 226B

조금 더 직관적인 코드

 

x = int(input())
dp = [0 for _ in range(x+1)]
for i in range(2, x+1):
    dp[i] = dp[i-1] + 1
    if i % 3 == 0:
        dp[i] = min(dp[i], dp[i//3] + 1)
    if i % 2 == 0:
        dp[i] = min(dp[i], dp[i//2] + 1)

print(dp)
print(dp[x])

 

방법 3 - 메모리 30864KB / 시간 68ms / 코드 길이 165B

방법 1과 방법2는 아래에서부터 하나씩 모두 구해 n까지 직접 구하는 방식이라면 방법 3은 필요한 부분에 따른 bfs를 하고 이에 따른 Memorization을 적용하는 방식이다.

이에 따라 더 적은 메모리와 시간을 소모한다.

 

r이라는 dict를 넣고 2로 나눴을 대와 3으로 나눴을 때의 bfs 함수값을 구한다.

이때, n%2 혹은 n%3 나머지를 넣는 이유는 그만큼의 -1 횟수를 의미로 구분하기 위해서이다.

예를 들어 11의 경우

1)

bfs(11//2=5)를 진행하고 -1을 적용하는 11%2=1을 기입한다.

이말인즉슨 -1을 1번 적용한 후 bfs(5)에 해당하는 값을 리턴한다는 뜻

"%2 1회 + -1 1회 적용한다."

2)

bfs(11//3=3)를 진행하고 -1을 적용하는 11%3=2을 기입한다.

이말인즉슨 -1을 2번 적용한 후 bfs(3)에 해당하는 값을 리턴한다는 뜻

"%3 1회 + -1 2회 적용한다." 

 

n = int(input())
r = {1:0, 2:1}
def bfs(n):
    if n in r:
        return r[n]
    m = min(bfs(n//2)+n%2, bfs(n//3)+n%3) + 1
    r[n] = m
    return m

print(bfs(n))