백준 1463번: 1로 만들기 (Python)

접근

단계별 이전 동적계획법 문제들과 유사한 문제였다.

2021.03.28 - [SW/백준 (Python)] - 백준 2579번: 계단 오르기 (Python)

백준 2579번: 계단 오르기 (Python)

입력된 N이 될 수 있는 경우의 수는 다음과 같다.

1. N이 2로 나누어 떨어질 경우 P(N) = P(N // 2) + 1 (N / 2 의 연산 최소값 + 2로 나누는 연산)
2. N이 2로 나누어 떨어지지 않을 경우 P(N) = P((N - 1) // 2) + 2 (N / 2 의 연산 최소값 + 1을 한번 빼는 연산 + 2로 나누는 연산)
3. N이 3으로 나누어 떨어질 경우...
4. N이 3으로 나누어 나머지가 1일 경우...
5. N이 3으로 나누어 나머지가 2일 경우...

숫자 N을 1로 만드는 연산의 최소값은 위 5가지 경우 중 최소값이다.

2022.09.23 다시 풀기

다시 풀어보니 아주 비효율적인 코드였다.

그냥 n 에서부터 연산이 한번 진행되었을 때 가능한 숫자들을 모아서 중복 제거를 위해 set 으로 만들고, cnt 를 하나씩 올리면 쉽고 빠르게 문제를 해결할 수 있다.

코드

다시 풀기 코드

n = int(input())
cnt = 0
seta = set([n])
while 1 not in seta:
    setb = set()
    for i in seta:
        if i % 2 == 0:
            setb.add(i // 2)
        if i % 3 == 0:
            setb.add(i // 3)
        setb.add(i - 1)
    seta = set(setb)
    cnt += 1
print(cnt)

기존 코드

import sys


n = int(sys.stdin.readline())
p = []
p.append(0)
p.append(0)  # 1을 만드는 연산의 최소값은 0
for i in range(2, n + 1):
    temp = []
    if i % 2 == 0:
        temp.append(p[i // 2] + 1)
    else:
        temp.append(p[(i - 1) // 2] + 2)
    if i % 3 == 0:
        temp.append(p[i // 3] + 1)
    elif i % 3 == 1:
        temp.append(p[(i - 1) // 3] + 2)
    else:
        temp.append(p[(i - 2) // 3] + 3)
    p.append(min(temp))
print(p[n])

더 생각해 볼 것?

...