[실버 III] 1463. 1로 만들기

 문제 

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

1463번: 1로 만들기

 사용 언어 

Python3

 풀이 과정 

처음엔 아래와 같이 또 재귀로 모든 경우의 수를 나눠 연산하려 했는데 숫자가 커지니 recursion error를 냈다.. 재귀 처음엔 어렵더니 계속 쓰게 되는데 DFS가 아니라면 안쓰도록 노력해봐야겠다.

if x in count:
         return count[x]
 else:
     if x % 3 == 0 and x % 2 != 0: # 3의 배수만일 때
         count[x] = 1 + min(makeOne(x//3), makeOne(x-1))
     elif x % 2 == 0 and x % 3 != 0: # 2의 배수만일 때
         count[x] = 1 + min(makeOne(x//2), makeOne(x-1))
     elif x % 2 == 0 and x % 3 == 0: # 6의 배수일 때
         count[x] = 1 + min(makeOne(x//3), makeOne(x//2), makeOne(x-1))
     else: # -1만 가능할 때
         count[x] = 1 + makeOne(x-1)
     return count[x]

그래서 값을 갈아끼우는 방식으로 바꿨고,

메모리랑 시간이 너무 크지만 맞았습니다!! ㅋㅋㅋㅋㅋ

풀긴 풀었지만 아래 다른 사람의 답안으로 더 공부했다.

 제출 답안 

from sys import stdin

N = int(stdin.readline())

# sequence = [N]
def makeOne(x):
    count = {1: 0} # 1은 1을 만들기 위해 연산이 0번 필요함
    sequence = [0 for _ in range(N+1)]

    for i in range(2, x+1):
        # -1만 가능할 때
        count[i] = 1 + count[i-1]
        sequence[i] = i-1
        if i % 3 == 0 and count[i//3] + 1 < count[i]: # 3의 배수이고 -1의 경우보다 작을 때
            count[i] = 1 + count[i//3]
            sequence[i] = i//3
        if i % 2 == 0 and count[i//2] + 1 < count[i]: # 2의 배수만일 때
            count[i] = 1 + count[i//2]
            sequence[i] = i//2

    return count[N]

print(makeOne(N))

 다른 사람 답안 

너비우선탐색 방식으로 풀이한 사람의 코드를 보았는데 훨씬 효율적이었다.

a = int(input())
lst = [a]
v = [0] * (10 ** 6 + 1) # 문제에서 주어진 최대 숫자로 배열 생성
v[a] = 1 
temp = 0

while v[1] == 0: # 1을 방문할 때까지
    new_lst = []
    
    for num in lst:
        v[num] = 1 # 방문처리
        if num % 3 == 0 and v[num // 3] == 0:
            v[num // 3] = 1
            new_lst.append(num // 3) # for문 안에서는 pop을 하면 문제가 생기기 때문에 리스트를 하나 더 만들어서 필요한 숫자만 append
        if num % 2 == 0 and v[num // 2] == 0:
            v[num // 2] = 1
            new_lst.append(num // 2)
        if v[num - 1] == 0:
            v[num - 1] = 1
            new_lst.append(num - 1) 
            
    temp += 1
    lst = new_lst
    
print(temp)

출처: 백준 정답자 풀이

 

동적계획법 문제를 풀다 보니 대부분 깊이우선탐색/너비우선탐색으로도 풀이가 가능한데 효율성은 후자가 훨씬 좋다는 느낌을 받았다. 내 코드랑 차이가 아주아주 많이 난다😂