백준 1463번 1로 만들기

시간초과 된 풀이

처음에는 deque를 이용해 문제를 해결하려 했다
시간초과가 날 거라고 어렴풋이 알고 있었다...

from collections import deque

n = int(input())
operation = deque([(n, 0)])

while True:
    num, cnt = operation.popleft()
    if num == 1:
        print(cnt)
        break
    if num % 3 == 0:
        operation.append((num//3, cnt+1))
    if num % 2 == 0:
        operation.append((num//2, cnt+1))
    operation.append((num-1, cnt+1))

주어진 n이 10이라고 했을 때,
0번 연산을 했을 때 값이 10이기 때문에 deque에 (10, 0)을 넣어주었다
그 후, while 문을 반복하며 일어날 수 있는 연산의 모든 경우를 deque에 담아가며,
값이 1이 되었을 때의 cnt를 출력해 주었다

어케 풀지

그리디 방식으로 보다 높은 수로 나누어지는 수로 나누어 나갈까 생각했지만,
문제에서 이미 그 방법에 대한 반례를 제공하고 있다
10 일 경우

① 높은 수로 나누어 떨어지면 나눈다
10 -> 5 -> 4 -> 2 -> 1

② 다른 방식
10 -> 9 -> 3 -> 1

①번 방식은 4번의 연산, ②번 방식은 3번의 연산으로 ②번 방식에서 연산 횟수가 최소가 된 것을 볼 수 있다

DP 풀이

이 문제는 동적 프로그래밍 기법을 이용해서 해결할 수 있었다

n 이 10 일때 10에서 부터 연산하며 내려오는 것이 아닌 ,
1에서 10까지 올라가며 각 숫자일 때의 연산 횟수의 최솟값을 저장해두는 것이다

• dp[i] 를 i 에서의 연산 횟수의 최솟값으로 설정했다

dp = [0] * (n+1)

• 현재 숫자와 배열의 index를 일치시키기 위해 dp[0]을 비워두고 dp[1]부터 dp[10]까지를 사용 할 것이다

for i in range(2, n+1):
    dp[i] = dp[i-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)

• 반복문을 왜 2부터 시작해야 할까?
  위에서 말했듯 1부터 시작해 주어진 10까지 올라갈 것이다
  즉 1은 연산을 0번 했을 때의 값이기 때문에, 이미 0으로 초기화 되어있는 dp[1]을 건들 필요가 없다

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

• 현재 숫자인 i 가 2나 3으로 나누어 떨어지지 않는다면 1을 더하는 방법을 사용해야 한다
  1을 더한 연산을 수행했으니, 1에서 현재숫자-1에 도달할 때의 연산 횟수의 최솟값인 d[i-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)

• 2나 3으로 나누어 떨어진다면 나누어 주는게 연산 횟수를 줄일 방법이 될 수 있다

  8을 예로 들 때,
  1에서 7까지의 최소 연산 횟수에서 1을 더해주는 것과,
  8을 2로 나눈 4 즉, 1에서 4까지의 최소 연산 횟수에서 1을 더해주는 방법이 있다
  따라서 dp[i] 와 dp[i // 2] + 1 중 더 작은 수를 dp[i]에 넣어준다

전체 코드

n = int(input())

dp = [0] * (n+1)

for i in range(2, n+1):
    dp[i] = dp[i-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])