[백준] 1463 1로 만들기 (DP) - Python / 자세한 설명 / 여러가지 풀이 / 실버1

백준 로고

 

 

 

Contents

 

 

---

 

1. 문제 정의 및 예제 해석

(문제 링크: https://www.acmicpc.net/problem/1463)

1463번: 1로 만들기

예제 입력과 출력

주어진 수 x에 대해, 아래 3가지 연산을 통해 1을 만듭니다. 이때, 연산을 사용하는 횟수의 최솟값을 출력합니다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

예제 입력 2번의 10을 보면, 10 -> 9 -> 3 -> 1로, 3번 연산이 최솟값입니다.

 

2. DP - BottomUp 풀이(for문 사용)

x=int(input()) # 수 입력받기
d=[0]*(x+1) # 1-based
for i in range(2,x+1): # 2부터 x까지 반복
    d[i]=d[i-1]+1 # 1을 빼는 연산 -> 1회 진행
    if i%2==0: # 2로 나누어 떨어질 때, 2로 나누는 연산
        d[i]=min(d[i],d[i//2]+1)
    if i%3==0: # 3으로 나누어 떨어질 때, 3으로 나누는 연산
        d[i]=min(d[i],d[i//3]+1)
print(d[x])

* 코드 설명

x에 수를 입력받습니다. dp리스트인 d를 0이 (x+1) 개 있는 리스트로 초기화합니다. d는 인덱스의 숫자가 1이 되는데 필요한 연산의 최솟값을 갖습니다. 즉, d[1]은 0으로 1이 1로 되는데 필요한 연산은 0회이기 때문입니다. d[2]는 2가 1이 되는데 필요한 최소 연산 횟수인 1이 될 것입니다. 

for i in range(2, x+1): 을 통해 2부터 x까지 i로 반복합니다.

d[i]=d[i-1]+1 : d[i]는 숫자 i가 1이 되는데 걸리는 최소한의 연산 횟수를 저장해야 합니다. i에서 1을 빼면 i-1이 되므로, d[i-1]+1을 함으로써, d[i-1] (i-1이 1이 되는데 필요한 최소한의 연산) + 1 (i에서 1을 빼서 i-1이 되는데 필요한 연산 횟수 1회)로 초기화합니다. 예를 들어, d[3] = d[2] +1 이라고하면, 3에서 1을 빼는 1회 연산을 통해 2가 되므로, d[2] + 1은 3에서 1을 빼서 2가 되고, d[2] (2에서 1이 되는데 필요한 최소 연산 횟수)를 더해준 것입니다. 
if i%2==0:    d[i]=min(d[i],d[i//2]+1) : i가 2로 나누어 떨어질 때, d[i]와 d[i//2]+1중 최솟값을 d[i]에 저장합니다.

d[i]는 위에서 초기화한 d[i-1]+1값이 들어있습니다. 이것과 d[i//2]+1을 비교해 최솟값을 d[i]에 넣습니다. d[i//2]의 의미는 i가 2로 나누어 떨어진다고 조건문에서 확인했으니, i를 2로 나눈 값이 1이 되는데 걸리는 최소한의 연산 횟수를 의미합니다. 즉, d[i//2]+1은 i를 2로 나눈 값이 1이 되는데 걸리는 최소 연산 횟수 + i를 2로나누는 연산횟수 1회입니다.
if i%3==0:    d[i]=min(d[i],d[i//3]+1) : i가 3으로 나누어 떨어질 때, d[i]와 d[i//3]+1 중 최솟값을 d[i]에 저장합니다.

현재 d[i]는 d[i-1]+1과 i가 2로 나누어 떨어지는 경우, d[i//2]+1중 최솟값이 들어있습니다. 여기에 i가 3으로 나누어 떨어지는 경우 d[i//3]+1과도 값을 비교해 최솟값을 d[i]에 넣습니다.

 

이렇게 for문을 반복하면 d[x]에는 x가 1이 되는데 필요한 연산의 최소 횟수가 들어갑니다.

 

3. DP - TopDown 풀이 (재귀 사용)

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를 딕셔너리로 초기화합니다. dp가 1일 때, 0 값을 갖는 것의 의미는 1일 때 1이 되는데 필요한 연산 횟수가 0회라는 것입니다. rec함수는 숫자 n을 입력받아, 재귀적으로 dp 딕셔너리를 채워갑니다. rec함수의 종료 조건은 입력받은 n이 dp딕셔너리의 key에 존재하는 경우 dp[n]을 리턴합니다. 

if (n%3==0) and (n%2==0): 
        dp[n]=min(rec(n//3)+1, rec(n//2)+1)

-> n이 3으로도 나누어 떨어지고, 2로도 나누어 떨어지는 경우, rec(n//3)+1, rec(n//2)+1중 최솟값을 dp[n]에 넣습니다. rec(n//3)+1이 의미하는 것은 n을 3으로 나눈 몫이 1이 되는데 필요한 최소 연산 횟수 + n을 3으로 나누는 연산횟수 1회입니다. 즉, 3으로 나눈 경우와 2로 나눈 경우중 연산 횟수가 더 적은 쪽이 dp[n]에 들어갑니다.
    elif n%3==0:
        dp[n]=min(rec(n//3)+1, rec(n-1)+1)

-> n이 3으로만 나누어 떨어지는 경우는 3으로 나눈 경우(rec(n//3)+1)와 n에서 1을 뺀 뒤, n-1이 1이 되는데 걸리는 최소 연산 횟수인 rec(n-1)+1을 비교하여 최솟값을 dp[n]에 넣습니다.
    elif n%2==0:
        dp[n]=min(rec(n//2)+1, rec(n-1)+1)

-> n이 2로만 나누어 떨어지는 경우도 마찬가지로 n을 2로 나눈 경우와 n에서 1을 뺀 경우를 비교하여 최솟값을 dp[n]에 넣습니다.
    else:
        dp[n]=rec(n-1)+1

-> n이 3으로도 나누어 떨어지지 않고, 2로도 나누어 떨어지지 않는 경우는 n에서 1을 뺀 값인 n-1이 1이 되는데 걸리는 최소한의 연산 횟수 + 1회(n에서 1을 빼는 연산 1회)를 dp[n]에 넣어줍니다.

    return dp[n]

-> 마지막 return dp[n]은 재귀 호출을 모두 마무리하고, rec(x)의 결과를 최종 반환할 때 쓰입니다.

 

4. BFS 풀이

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])

 

* 코드 설명

BFS 풀이는 Q에 x값을 넣고, x에서 1로 갈 때 최단거리를 찾는 방향입니다. BFS로 탐색한 결과는 항상 최단거리를 보장하기 때문에 이렇게도 풀어보았습니다. 즉, x부터 BFS를 돌며, visited에 방문 표시와 해당 노드에 방문하는데 걸린 횟수를 함께 저장합니다.

 

예를 들어, x가 10일 때, 2로 나누어 떨어지니까 visited[5]에는 1이 들어갑니다. 10에서 1을 빼면 visited[9]에도 1이 들어갑니다. 그러고 Q에는 각각 5와 9가 들어갑니다. 5일 때는 1을 빼는 연산을 한 번 더 하기 때문에, visited[4]에는 2가 들어갑니다. 9는 3으로 나누어 떨어지니까 visited[3]에도 2가 들어갑니다. 9에서 1뺀 visited[8]에도 2가 들어갑니다. 그러면 현재 Q에는 4,3,8이 들어있습니다. 이중 3에서 3으로 나누어 떨어지니까 바로 1이 되며, visited[1]에는 3이 들어갑니다. 그래서 최종적으로 visited[1]을 출력하면 정답입니다. 

 

5. 느낀 점

이 문제는 DP의 2가지 유형인 보텀업(for문 사용), 탑다운(재귀 사용)으로도 문제를 풀어보았고, BFS로도 풀어보았습니다. 사실 처음에 풀었을 땐, BFS밖에 떠오르지 않아 BFS로 풀었는데 다들 DP로 풀었길래, DP 풀이를 보고 이해하며 풀었습니다. 보텀업과 탑다운이 다 되는 문제로, DP를 연습하기 참 좋은 문제라는 느낌이 들었습니다. 내가 왜 이걸 이렇게 여러 풀이로 풀고 있는지 갑자기 현자 타임이 오는 밤입니다.

 

읽어주셔서 정말 감사합니다.

다음에 더욱 재미있고 유익한 글로 찾아오겠습니다.