문제 이해
문제
정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.
X가 3으로 나누어 떨어지면, 3으로 나눈다.
X가 2로 나누어 떨어지면, 2로 나눈다.
1을 뺀다.
정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.
입력
첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.
출력
첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.
문제 접근
문제를 보고 이거 그냥 단순한 BFS문제구나? 해서 바로 BFS로 풀었다.
근데 다 풀고나서 제출 후에 검색해보니 DP로 많이들 풀어서 나도 DP로도 풀어봤다.
BFS
BFS로 푸는 방식은 좀 직관적이다.
시작하는 수 N을 큐에 넣고 1을 감소시키기, 2로 나눌 수 있다면 나누기, 3으로 나눌 수 있다면 나누기를 모두 수행하고 각각의 visited 배열에 몇번째로 값이 들어가는지를 입력해두면 된다.
DP
DP로 푸는 방식은 사실 BFS와 크게 차이가 있지는 않다. 이 또한 3가지 연산을 모두 진행하고 그중 가장 작은 DP를 선택하는 방식이다.
문제 풀이
BFS
visited에 N에서 몇번 연산을 진행하여 i까지 도달했는지를 visited[i]에 저장한다.
이렇게 되면 visited[1]에 N에서 1까지 몇번의 연산이 필요한지의 최솟값이 저장된다.
cur이 1이 되면 break를 통해 함수를 종료시킨다.
import sys
from collections import deque
N = int(sys.stdin.readline())
visited = [0 for i in range(N+1)]
def bfs():
q = deque()
q.append(N)
while q:
cur = q.popleft()
if cur==1:
break
if cur%3==0 and visited[cur//3]==0:
visited[cur//3] = visited[cur] + 1
q.append(cur//3)
if cur%2 == 0 and visited[cur//2]==0:
visited[cur//2] = visited[cur] + 1
q.append(cur//2)
if visited[cur-1]==0:
visited[cur-1] = visited[cur] + 1
q.append(cur-1)
bfs()
print(visited[1])
DP
2부터 시작하는데 d[1]이 0이고 d[2]가 1이므로 이 두 값을 알기 때문에 bottomup방식을 사용한다.
d[i]에 처음에는 1로 증가시키는 연산을 넣고, 그 뒤에 2로 나눠진다면, 현재의 d[i]와 d[i//2]에 연산 횟수 1번을 더한 값을 비교하여 더 작은 값을 d[i]에 입력한다. 3으로 나누는 연산도 똑같이 진행한다.
이렇게 되면 d[N]에는 1이 N이 되기 위한 최소연산수가 들어가게 된다.
import sys
N = int(sys.stdin.readline())
d = [0] * (N+1)
for i in range(2, N+1):
d[i] = d[i-1] + 1
if i % 2 == 0:
d[i] = min(d[i], d[i//2] + 1)
if i % 3 == 0:
d[i] = min(d[i], d[i//3] + 1)
print(d[N])제출 코드
개인적으로 나는 BFS가 편해서 BFS로 풀었는데 DP로 푸는 방식도 연습해볼 수 있는 기회였고, 확실히 코드길이가 줄어드는 것을 볼 수 있었다.
하지만 두 코드 모두 제출해봤을 때 BFS가 더 적은 시간을 소요하는 것을 확인할 수 있었다.
