백준 실버3 문제입니다. 실전에 대비하기 위해 60분 시간제한을 두고 풀었습니다.

문제

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

[나의 풀이]

⌛ 시간 초과 (알고리즘 구현 O, 시간복잡도 해결 X)

from collections import deque

N = int(input())
mem = [0 for _ in range(N+1)]

def make_one(x):
    queue = deque([[1,0]])

    while queue:
        v, cnt = queue.popleft()
        
        if v==x: 
            return cnt
        
        queue.append([v*3,cnt+1])
        queue.append([v*2,cnt+1])
        queue.append([v+1,cnt+1])

for i in range(1,N+1):
    mem[i] = make_one(i)
print(mem[N])

입력된 수(N)를 (1)3으로 나누거나 (2) 1로 나누거나 (3) 1을 빼어 1로 만들 수 있는 최소 횟수를 구하는 문제입니다.🐣🐣🐣

Queue를 활용한 BFS 알고리즘을 통해 1부터 N까지의 수들을 1로 만들 수 있는 최소 횟수를 구하여 해결하였습니다.

하지만 대부분 케이스 시간 초과가 발생하여 다른 풀이를 참고하였습니다.

[다른 사람의 풀이1]

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

DP를 활용하여 시간 초과를 해결할 수 있었습니다.

먼저, 1~N+1까지 정수들을 1로 만들 수 있는 최소 횟수를 저장할 리스트(d)를 초기화합니다.🦌🦌🦌

정수 1은 0번만에 1을 만들 수 있으므로 제외하고 2부터 N까지 최소 횟수를 구하기 위해 그리디 방식으로 진행됩니다.

연산 가능한 3가지 방식 조건별로 확인해야 합니다. 이때 1을 뺏셈하여 연산할 수 있는 조건이 있음과 동시에 Botton-Up DP 방식이기 때문에, 직전 정수(현재 정수-1)의 최소 횟수에 +1 한다면 현재 정수의 최소 횟수와 상관없이 1을 만들 수있기 때문에 일단 저장합니다.

그 다음으로, 직전 정수(현재 정수-1)가 아닌 2로 나눈 정수(현재 정수//2) 혹은 3으로 나눈 정수(현재 정수//3)에도 값이 존재할 때의 값을 비교하여 각 3가지 연산별 최소값으로 초기화하면 됩니다.

이렇게 Botton-Up DP+그리디 방식으로 각 정수별 1이 될 수 있는 최소 연산 횟수(d)를 빠르게 구하고 입력된 N에 해당하는 횟수를 출력하면 정답을 도출할 수 있습니다.

[다른 사람의 풀이2]

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

'다른 사람의 풀이1'과 같이 DP+그리디를 활용하되 재귀함수를 활용한 Top-Down 방식의 풀이입니다.🐨🐨🐨

1~N까지 1로 만들 수 있는 최소 횟수를 dict형태(dp)로 기억하고 x를 바로 대입하여 재귀시키는 알고리즘입니다.

연산할 수 있는 3가지 조건을 구현하는 방법은 유사하나, 1로 만들 수 있는 최소 횟수를 dict형태(dp)로 저장했기 때문에

if n in dp.keys():
	return dp[n]

최소 횟수를 구한 정수가 이미 존재한다면(dp.keys()) 바로 return 하여 시간복잡도를 줄인 모습입니다.

감사합니다.