프로그래머스 algorithm study python dp

파이썬 알고리즘 : 점프와 순간 이동

수학적 사고

2024년 3월 4일 알고리즘 문제풀이

문제

난이도

Lv.2

코드

일반적인 DP문제라고 생각했다. 조금 어려운 편이긴 하지만, 기존에 충분히 풀어봤던 유형이라 금방 풀 수 있었다. 도착지로 이동하는 마지막 방법을 점프라고 고정하고 생각했다.

1차

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

def solution(n):
    # 3칸까지는 고려할 필요 없음
    if n <= 3:
        dp = [0, 1, 1, 2]
        return dp[n]
    
    # 그 이상일 때는 DP
    # 가장 최대 건전지 사용량은 그곳까지 점프로만 도달했을 때이므로 모든 곳을 최댓값으로 초기화한다.
    dp = []
    for i in range(n + 1):
        dp.append(i)
    # 2,3일 때는 알맞게 초기화
    dp[2] = 1
    dp[3] = 2

    # 4 이상일 때부터 DP
    for i in range(4, n + 1):
        # 반으로 나누었을 때 몫
        k = i // 2
        # 홀수여서 딱 절반인 곳이 존재하지 않을 때
        if i % 2:
            # i까지 도달 비용 = 몫까지 도달하는 비용(dp[j]) + 몫부터 i까지 점프하는 비용(i-j)
            for j in range(k, i):
                dp[i] = min(dp[i], dp[j] + i - j)
        # 짝수여서 절반인 곳이 존재할 때
        else:
            # 절반인 곳에서 순간이동하면 도착할 수 있으므로 절반에 도착하는 것과 같은 값
            dp[i] = min(dp[i], dp[k])
            for j in range(k + 1, i):
                dp[i] = min(dp[i], dp[j] + i - j)
    return dp[n]

n칸 까지 갈 때, 절반인 n//2를 기준으로 생각하면 된다. 절반도 오지 못했을 떄 점프를 하는 것은 거기서 순간이동 하는 것보다 더 건전지 사용량이 소모될 것이기 때문이다. 예를 들어, 10 칸을 이동한다고 했을 때

  1. 4칸 + (6칸을 점프) = 10칸 도착

이라는 시나리오는 고려할 필요가 없다는 의미이다.

  1. 4칸 + (순간이동하여 8번째 칸으로 이동) = 8칸도착

  2. 8칸 + (2칸을 점프) = 10칸

목적지의 절반을 도달하지 못했을 때는 항상 이 경우가 존재하기 떄문에 반복에서 제외했다. 따라서 목적지의 절반 이상일 때만 고려했다. 하지만 딱 절반일 때가 존재할때는 특별한 분기로 처리했다. 딱 절반인 지점에서 순간이동하면 곧바로 도착하기 떄문에, 절반 까지의 건전지 소모량으로 도착할 수 있기 떄문이다.

정확도에선 모두 맞았으나, 효율성에서 모두 시간초과되어 60/100점 처리되었다.

2차

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

def solution2(n):
    # 추가된 로직 : 2르 최대한 나눈다.
    while True:
        if not n % 2:
            n //= 2
        else:
            break
            
    if n <= 3:
        dp = [0, 1, 1, 2]
        return dp[n]
    dp = []
    for i in range(n + 1):
        dp.append(i)
    dp[2] = 1
    dp[3] = 2

    for i in range(4, n + 1):
        k = i // 2
        if i % 2:
            for j in range(k, i):
                dp[i] = min(dp[i], dp[j] + i - j)
        else:
            dp[i] = min(dp[i], dp[k])
            for j in range(k + 1, i):
                dp[i] = min(dp[i], dp[j] + i - j)
    return dp[n]

효율성을 높이기 위해, 불필요한 경우를 최소화했다. 도착지점이 짝수일 때는, 그 절반지점까지 가는데 소모되는 비용과 동일하다. 순간이동으로 건전지 사용 없이 도착할 수 있기 때문이다. 따라서 목적지를 나눌 수 있을 때까지 2로 나누면 dp를 덜 실행해도 된다. 예를 들어, 100칸까지 가는 비용은 50칸까지, 25칸까지 가는 비용과 동일하다.

3차

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

def solution3(n):
    while True:
        if not n % 2:
            n //= 2
        else:
            break
    if n <= 3:
        dp = [0, 1, 1, 2]
        return dp[n]
    dp = []
    for i in range(n + 1):
        dp.append(i)
    dp[2] = 1
    dp[3] = 2

    for i in range(4, n + 1):
        # 변경된 로직
        # 현재 구하는 지점이 홀수라면, 바로 전(짝수)에서 1칸 점프하면 된다.
        if i % 2:
            dp[i] = dp[i - 1] + 1
        else:
        # 현재 구하는 지점이 짝수라면, 2로 나눈 절반까지와 비용이 동일하다.
            dp[i] = dp[i // 2]
    return dp[n]

1차 시도에서 설명했지만, 탐색은 중간 이후의 지점만 하면 된다고 생각했었다. 문득, 문제가 풀리지 않아 고민한 끝에 두 가지 생각이 들었다.

  1. 최솟값을 탐색하는 과정에서도 분명 짝수를 만나지 않을까?
  2. 점프와 순간이동이 섞여있다면 어떤 규칙은 없을까?

예를 들어, 10칸까지 간다고 했을 때 탐색은

  1. 5칸까지 이동할 수 있는 최솟값(이 후는 순간이동을 하면 되기 때문에 점프를 하지 않는다)

  2. 6칸까지 이동할 수 있는 최솟값 + 4칸 점프하는 건전지 사용량

  3. 7칸까지 이동할 수 있는 최솟값 + 3칸 점프하는 건전지 사용량
  4. 8칸까지 이동할 수 있는 최솟값 + 2칸 점프하는 건전지 사용량
  5. 9칸까지 이동할 수 있는 최솟값 + 1칸 점프하는 건전지 사용량

중 하나를 고르게 된다. 6칸, 8칸은 짝수이므로 6칸까지 이동할 수 있는 최솟값은 3칸까지 이동할 수 있는 최솟값과 같다. 8칸까지 이동할 수 있는 최솟값은 4칸까지 이동할 수 있는 최솟값과 같으며 2칸까지 이동할 수 있는 최솟값과도 같게 된다. 여기서, 현재 방식으로 탐색하는 것은 정답이 아닐 것 같다는 생각이 들었다. 규칙성이 너무 흐릿하고, 혹여나 있다해도 너무 복잡해서 출제자가 원하는 바는 아닐거라는 생각이 들었다.

그래서 거꾸로 생각했다.

  1. n을 줄이기 위해, 가능할 때 까지 절반으로 나누어 홀수로 만들었다.
  2. 더이상 나누지 못하는 이유는 홀수기 때문이다.
  3. 딱 한칸만 옆으로 가면 짝수가 되서 다시 반으로 나눌 수 있다.
  4. 반복되면 언젠가 1에 도착하지 않을까?

건전지 사용을 최소로 하는데 가장 중요한 것은 점프를 최소화 해야한다. 방향을 거꾸로 보는게 좋다고 생각한 이유는, 순간이동과 점프를 고민하게 만드는 것은 도착지점을 지나가는 것 때문이었다. 거꾸로 점점 숫자가 작아진다면 1이 최종지점으로 정해져 있어서 이 걱정이 사라진다. 한 가지 신경써야 할 것은, 보통 DP에서 3(때론 5)까지는 일반적인 규칙성이 적용되지 않기 떄문에 무조건 1로 도착하기 보단 3이하에 도착하면 내가 계산한 수를 반환하도록 처리했다.

최종

1
2
3
4
5
6
7
8
9
10
11

def solution(n):
    cnt = 0
    while n > 3:
        if not n % 2:
            n //= 2
        else:
            cnt += 1
            n -= 1
    if n <= 3:
        dp = [0, 1, 1, 2]
        return dp[n] + cnt

맞춰놓고 신기했다. 이게 되네? 이걸 한번에 생각한 사람은 얼마나 천재일까…

다 풀고나니 정방향으로 생각하면 어떤 로직일지 고민해봤다.

  • 매 칸에서,
    • 만약 현 위치에서 순간이동 해도 도착지점을 지나치지 않는다면?
      • 한 칸 점프하고 순간이동 했을 때도 도착지점을 지나지 않는다면
        • 한 칸을 점프하고 순간이동한다(그냥 순간이동하는 것보다 1을 소모하고 2칸을 더 갈 수 있다.)
      • 한 칸 점프하고 순간이동하면 도착지점을 지나게 된다.
        • 그냥 순간이동한다.

를 반복하면 될 것 같다. 그냥 역방향으로 생각하는게 속 편하겠다.

CATALOG
    algorithm