[백준 - Python] 1463. 1로 만들기 (DP)

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

1463번: 1로 만들기

 

코드

n = int(input())
d = [0] * (n + 1)  # d[i]에 저장되는 값은 i를 1로 만드는 최소 연산 횟수

# 상향식 풀이 : 제일 작은 인덱스의 수부터 목표하는 값으로 향하는 것
for i in range(2, n + 1):
    # if 문을 하지 않아도 밑의 조건문에서 최소값으로 교체되기 때문에 어짜피 셋 다 시도하는 것과 같으 결과
    d[i] = d[i - 1] + 1
    if i % 3 == 0:
        d[i] = min(d[i], d[i // 3] + 1)
    if i % 2 == 0:
        d[i] = min(d[i], d[i // 2] + 1)

print(d[n])

 

동적 계획법은 상향식과 하향식이 있는데,

이 문제는 1에 대한 dp값을 알기 때문에 상향식 풀이를 선택했다.

 

상향식은 제일 작은 인덱스의 수부터 목표값으로 향하는 방식이고

하향식은 맨 위의 값에서 재귀로 작은 인덱스로 향하는 방식이다.

 

이 문제는 연산 횟수의 최솟값을 구해야 한다는 점에서

그리디 문제 같아 보였지만,

문제에서 주어진 힌트를 보면 그리디 풀이가 적절하지 않다는 것을 확인할 수 있다.

 

다시 말해, 최선의 연산 방법이 정해져 있지 않기에,

모든 경우를 전부 시도해봐야 한다.

 

 

가능한 3가지 연산을 수행하는 모든 경우들 중에서

연산 횟수가 가장 적은 경우를 찾아내기 위해

동적 계획법을 사용하면서 조건문으로 최소 연산 횟수를 저장해준다.

 

코드를 보면,

우선 dp 리스트를 선언해주는데

d[i]에 저장되는 값은 i를 1로 만드는 최소 연산 횟수이다.

 

상향식(바텀업) 풀이법을 사용할 것이므로 2부터 n까지 차례대로 반복문을 이용해

최소 연산 횟수를 저장해준다.

 

반복문 내의 코드를 설명하기 이전에

문제에서 주어진 힌트를 예시로 부연 설명을 해보자면,

X = 10 인 경우, 10 → 9 → 3 → 1 의 과정을 거쳐 1이 되게 되는데

9의 경우에는 9 → 3 → 1 의 과정을 거치며

3의 경우에는 3 → 1 의 과정을 거친다.

 

다시 말해, dp[10]을 구할 때는 dp[9] 값을,

dp[9]를 구할 때는 dp[3] 값을 이용한다.

 

연산의 과정은 큰 수에서 작을 수 방향으로 이루어지지만,

우리가 DP 테이블을 통해 저장하고자 하는 값은 연산 횟수이기 때문에

상향식으로 앞에서 구한 결과값을 저장하였다가 후에 사용해야 한다.

 

일단, 2와 3으로 나누어떨어지지 않는 경우에는

무조건 1을 빼야하므로 기본적으로

dp[i] = dp[i - 1] + 1을 통해 연산 횟수를 하나 늘려주는데

 

dp[i]가 2 혹은 3으로 나누어 떨어진다면,

1을 빼는 경우와 나누었을 경우 중에서 최소값을 선택한다.

 

각각의 조건문에서 1을 더하는 이유는

dp 리스트는 연산 결과가 아닌 연산 횟수를 저장하기 때문이다.

 

각 연산에 대한 조건들은 if ~ else 문으로 묶으면 안된다.

왜냐햐면 묶지 않고 개별 조건문으로 해주어야

두 연산을 모두 수행해보고

그 중에서 제일 최소인 경우를 선택할 수 있기 때문이다.

 

 

탑다운 방식 풀이

x = int(input())
dp={1:0}
def rec(n):
    if n in dp.keys():
        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))

 

dp를 딕셔너리로 활용하는 탑다운 방식의 풀이가 있어서 가져와봤다.

 

 

BFS 풀이

x에서 1로 가는 최단 거리 문제라고 생각한다면 BFS 풀이도 떠올릴 수 있다.

x부터 BFS를 돌며 visited에 방문 표시 및 해당 노드에 방문하는데 걸리는 연산 횟수를 저장한다.

from collections import deque

x = int(input())
Q = deque([x])
visited = [0] * (x+1)

while Q:
    c = Q.popleft()
    if c == 1:
        break
        
    if c % 3 == 0 and visited[c // 3] == 0:
        Q.append(c // 3)
        visited[c // 3] = visited[c] + 1
        
    if c % 2 == 0 and visited[c // 2] == 0:
        Q.append(c // 2)
        visited[c // 2] = visited[c] + 1
        
    if visited[c - 1] == 0:
        Q.append(c - 1)
        visited[c - 1] = visited[c] + 1

print(visited[1])

 

x가 10인 경우를 생각해보면,

10은 2로 나누어 떨어지고 1을 빼는 것도 가능하므로,

visited[5] = 1이 되고 visited[9] = 1이 된다.

그리고 큐에 5, 9가 들어간다.

 

5일 때는 빼는 연산만 가능하므로,

visited[4] = 2가 되고

큐에 4가 들어간다.

 

9는 3으로 나누어지고, 1을 빼는 것도 가능하므로,

visited[3] = 2가 되고 visited[8] = 2가 되고

큐에 3, 8이 들어간다.

 

이 중에서 3이 3으로 나누어떨어지면 최종 목표인 1이 되고

 vistied[1] = 3이 되고

반복문을 탈출하여 visited[1]을 출력하면 된다!

 

 

참고 자료

https://bio-info.tistory.com/159

https://velog.io/@qtly_u/DP-%EB%B0%B1%EC%A4%80-1463%EB%B2%88-1%EB%A1%9C-%EB%A7%8C%EB%93%A4%EA%B8%B0

https://jae04099.tistory.com/199