[백준] 1463번 계단 오르기(feat. 다이나믹 프로그래밍, BFS)

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

 

문제 분석

• 첫 번째 단계 (문제 요약 및 조건 파악하기)

정수 X에 사용할 수 있는 연산은 3가지다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

정수 N이 주어졌을 때, 위의 세 연산을 적절히 사용해서 1을 만들려고 한다.
연산을 사용하는 횟수의 최솟값을 구해서 출력해야 한다.

입력을 보면, N의 범위는 1 <= N <= 1e6 이다.

그리고, 문제를 생각해보면, 
예를 들어 30을 1로 만드는 연산 과정 안에는
30보다 작은 수를 1로 만드는 연산이 포함되어 있다.

즉, 큰 문제를 작은 문제로 나눌 수 있고, (최적 부분 구조)
작은 문제를 구한 정답이  큰 문제를 구한 정답에서도 동일하기 때문에(중복 부분 문제)

이 문제는 DP 를 이용하여 풀 수 있을 것 같다.
DP테이블을 어떻게 정의할 수 있을까?

DP테이블의 크기를 n + 1 로 선언하고,
각 인덱스를 n이라고 가정하고, 해당 인덱스의 값에는 해당 인덱스를 1로 만드는데 필요한 연산 횟수를 저장한다.

예를 들어 d[1]은 0으로 1이 1로 되는데 필요한 연산은 0회이기 때문이다.
d[2]는 2가 1이 되는데 필요한 최소 연산 횟수인 1이 될 것이다.

 

• 두 번째 단계 (문제 핵심 파악하기)

연산을 진행할 때,
현재 n을 -1할지, // 3 할지, // 2 할지 각각 비교하여 가장 작은 값으로 dp테이블을 갱신할 수 있을 것이다.

그렇다면, 아래와 같이 경우를 나눌 수 있다.

1. n이 2와 3으로 나누어 떨어지는 경우,
2. n이 2로만 나누어 떨어지는 경우,
3. n이 3으로만 나누어 떨어지는 경우
4. n이 2와 3으로 나누어 떨어지지 않는 경우

이렇게 4가지로 나누어 dp 테이블을 갱신할 수 있을 것이다.

'''
정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지이다.
1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

정수 N이 주어졌을 떄, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 할 때,
연산을 사용하는 횟수의 최솟값을 구해서 출력해야 한다.

i)
가장 쉬운 방법으로는, 어떤 수N이 주어지면,
해당 N을 위에서 주어진 3개의 연산을 사용해서 연산을 사용할 때마다 횟수 변수에 +1로 카운팅을 하고 N이 1이 되었을 때의 count를 출력하면 될 것이다.

그런데, 문제이 입력 조건을 보면, n은 최대값이 10^6이다. 1000000(백만) 이다.
1000000에 대하여 위의 연산만을 이용하여 1을 만들려면, 시간 제한 0.15초 만에 해결 할 수 없을 것으로 예상된다.

즉, 다른 로직을 생각해 봐야 한다.
dp 테이블을 만들고, 해당 DP테이블의 각 요소값은, 해당 인덱스 값이 1이 되는데 필요한 연산 횟수를 저장한다.
예를 들어 d[1]은 0으로 1이 1로 되는데 필요한 연산은 0회이기 때문이다.
d[2]는 2가 1이 되는데 필요한 최소 연산 횟수인 1이 될 것이다.

n을 가능한 큰 수인 3으로 먼저 나누어 떨어진다면 해당 연산을 진행하는게 유리해보이지만, 실제로는 그렇지 않다.
3으로 나누어 떨어진다고해서 무조건 먼저 3으로 나눈 것이 이득이 아니다.

생각해보자.

n을 연산하여 1로 만들 때,
예를 들어 30을 생각해보자.
30을 3으로 나누면 10
10을 2로 나누면 5
5에서 1을 빼면 4
4를 2로 나누면 2
2에서 1을 빼면 1

총 5번의 연산을 진행했다.
하지만 30으로 1로 만드는 최소 연산 횟수는 5번이 아니다.
30을 3으로 나누면 10
10에서 1을 빼면 9
9를 3으로 나누면 3
3을 3으로 나누면 1
총 4번

30을 1로 만드는 최소 연산 횟수는 4번이다.

i)
그렇다면, 우리는 연산을 진행할 때,
현재 n을 -1할지, //3 할지, // 2 할지 비교하여 가장 작은 값으로 dp테이블을 갱신할 수 있을 것이다.
그렇다면,
1. n이 2와 3으로 나누어 떨어지는 경우,
2. n이 2로만 나누어 떨어지는 경우,
3. n이 3으로만 나누어 떨어지는 경우
4. n이 2와 3으로 나누어 떨어지지 않는 경우
이렇게 4가지로 나누어 dp테이블을 갱신할 수 있을 것이다.

구현 해보자.
'''

 

코드 구현(DP)

import sys

n = int(sys.stdin.readline().rstrip())

dp = [0] * int(n + 1)

for i in range(2, n + 1):
    if i % 2 == 0 and i % 3 == 0:   # 현재 i가 2와 3으로 나누어 떨어지는 경우
        dp[i] = min(dp[i // 2], dp[i // 3], dp[i - 1]) + 1
    elif i % 3 == 0:    # 현재 i가 3으로 나누어 떨어지는 경우
        dp[i] = min(dp[i - 1] + 1, dp[i // 3] + 1)
    elif i % 2 == 0:    # 현재 i가 2로 나누어 떨어지는 경우
        dp[i] = min(dp[i - 1] + 1, dp[i // 2] + 1)
    else:   # 현재 i가 2와 3으로 나누어 떨어지지 않는 경우
        dp[i] = dp[i - 1] + 1

print(dp[n])

 

코드 작성 (이 문제는 BFS로도 풀이할 수 있다.)

from collections import deque
x=int(input())
Q=deque([x])
visited=[0]*(x+1)
while Q:
    c=Q.popleft()
    if c==1:
        break
    if c%3==0 and visited[c//3]==0:
        Q.append(c//3)
        visited[c//3]=visited[c]+1
    if c%2==0 and visited[c//2]==0:
        Q.append(c//2)
        visited[c//2]=visited[c]+1
    if visited[c-1]==0:
        Q.append(c-1)
        visited[c-1]=visited[c]+1
print(visited[1])

BFS 풀이는 Q에 x값을 넣고, x에서 1로 갈 때 최단 거리를 찾는 방향이다.
BFS로 탐색한 결과는 항상 최단거리를 보장 하기 떄문에 이렇게도 풀이 할 수 있다.
즉, x부터 BFS를 돌며, visitied에 방문 표시와 해당 노드에 방문하는데 걸린 횟수를 함께 저장한다.

예를 들어, x가 10일 때, 2로 나누어 떨어지니까 visited[5]에는 1이 들어간다.
10에서 1을 빼면 visited[9]에도 1이 들어간다. 그리고 Q에는 각각 5와 9가 들어간다.
5일 떄는 1을 빼는 연산을 한 번 더 하기 때문에, visted[4]에는 2가 들어간다.
9는 3으로 나누어 떨어지니까 visited[3]에도 2가 들어간다. 9에서 1을 뺀 visited[8]에도 2가 들어간다. 
그러면, Q에는 4, 3, 8이 들어있다. 
이중 3에서 3으로 나누어 떨어지니까 바로 1이 되며, visited[1]에는 3이 들어간다. 그래서 최종적으로 visited[1]을 출력하면 정답이 된다.