[CLASS 3]백준 1463번 - 1로 만들기

1463번 : 1로 만들기

 

내 개인적인 생각으로 이 문제를 가장 명료하게 풀 수 있는 방법은 재귀인것 같다. 그러나 수가 커지면 너무나도 많은 재귀를 해야 하기 때문에 비효율적이다.

 

내 코드(재귀):

# 재귀(재귀스택 초과)
n = int(input())

def find(n):
    countList = []
    if n == 1:
        return 0
    
    countList.append(find(n-1) + 1)
    if n % 3 == 0:
        countList.append(find(n//3) + 1)
    if n % 2 == 0:
        countList.append(find(n//2) + 1)

    return min(countList)

print(find(n))

 

1이 아니라면 해당 수에서 1을 뺀값, 2로 나누어 떨어진다면 2로 나눈 값, 3으로 나누어 떨어진다면 3으로 나눈 값을 각각 리스트에 추가해서 다시 함수를 호출한 뒤 1을 더하여 리스트에 담고 최솟값을 반환한다.

 

 

내 코드(집합):

cache = set([int(input())])
count = 0
while True:
    temp = cache.copy()
    for i in temp:
        if i == 1:
            print(count)
            exit()
        
        cache.add(i-1)
        if i % 3 == 0:
            cache.add(i//3)
        if i % 2 == 0:
            cache.add(i//2)

    cache -= temp  
    count += 1

 

집합을 이용한다면 시간 초과에 걸리지 않고 통과할 수 있다. 먼저 count 변수에 0을 대입하고, 집합에 1을 뺀 값, 2로 나눈 값, 3으로 나눈 값을 넣은 뒤 기존에 있던 원소들을 제거한다. 이 과정을 한 번 반복할 때마다 count 변수에 1을 더하고, 집합에 1이 있다면 바로 count를 출력하고 종료하는 방법이다. 리스트에 저장해도 되지만 중복되는 수들로 인해 시간이 훨씬 오래 걸려서 set을 사용했다.

 

사실 이는 DP를 이용한 풀이라고는 보기 힘들다. 그냥 가능한 모든 경우를 다 계산하면서 가장 처음으로 1을 만들 수 있는 count 를 찾기 때문이다. DP 에 더 가까운 것은

 

infinitt님의 코드:

n = int(input())

dp = [0 for _ in range(n+1)]

for i in range(2, n+1):
    dp[i] = dp[i-1] + 1  

    if i%2 == 0 and dp[i] > dp[i//2] + 1 :
        dp[i] = dp[i//2]+1
        
    if i%3 == 0 and dp[i] > dp[i//3] + 1 :
        dp[i] = dp[i//3] + 1
        
print(dp[n])

 

이런 코드인 것 같다. 2부터 시작해서 해당 수를 만들 수 있는 가장 적은 횟수를 계속 만들어 나가면서 요청한 수에 도달하게 된다. 이게 출제자의 의도가 아닐까?