백준_python 1463번 1로 만들기(BFS, DP)

<문제 링크>

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

1463번: 1로 만들기

 

 

<정답 코드>

sol 1) BFS(너비 우선 탐색)

from collections import deque
 
n = int(input())
 
def bfs(x):
    visited = [False] * (n + 1)  # n + 1 크기의 방문 체크 배열 생성
    q = deque([(x, 0)])          # 큐에 초기 값과 연산 횟수 추가
    visited[x] = True            # 초기 값 방문 체크
 
    while q:
        tmp, cnt = q.popleft()
 
        if tmp == 1:  # 1에 도달하면 연산 횟수 반환
            return cnt
 
        # 3으로 나누기 연산
        if tmp % 3 == 0 and not visited[tmp // 3]:
            visited[tmp // 3] = True
            q.append((tmp // 3, cnt + 1))
 
        # 2로 나누기 연산
        if tmp % 2 == 0 and not visited[tmp // 2]:
            visited[tmp // 2] = True
            q.append((tmp // 2, cnt + 1))
 
        # 1 빼기 연산
        if tmp > 1 and not visited[tmp - 1]:  # tmp > 1 조건으로 범위 초과 방지
            visited[tmp - 1] = True
            q.append((tmp - 1, cnt + 1))
    
print(bfs(n))

 

 

 

sol 2) DP(다이나믹 프로그래밍)

def make_one_by_dp(n):
    d = [0] * (n + 1)
    d[1] = 0                # 1을 1로 만드는 데 필요한 연산 횟수는 0
 
    for i in range(2, n + 1):
        d[i] = d[i - 1] + 1  # 먼저 1을 빼는 연산
       
        if i % 3 == 0:
            d[i] = min(d[i], d[i // 3] + 1)  # 3으로 나누는 연산
        if i % 2 == 0:
            d[i] = min(d[i], d[i // 2] + 1)  # 2로 나누는 연산
        
    return d[n]
 
n = int(input())
print(make_one_by_dp(n))

DP 코드 진행 과정 출력 결과

 

 

< BFS vs DP >

[ 채점 결과 ] 

• 속도 : BFS가 더 빠름
• 메모리 : 비슷
• 코드 길이 : DP가 더 짧음

 

 

단계별로 살펴보면 DP의 최적 부분 구조(Optimal Substructure) 속성을 이용했음을 알 수 있다.