프로그래머스/Python) 숫자 타자 대회 Lv3 - DP풀이

💭 나의 접근 방법

---

5123 으로 이동해야하는 타자의 경우 5로 이동할 때 1을 고려해야 하기 때문에 왼쪽 오른쪽중 최선의 것을 고를수있는것이 불가능. 따라서 브루투포스는 불가

따라서 앞에서 나온 경로값을 가지고 있어야한다. 누적비용

→ DP

숫자 하나씩 처리하며, 왼손으로 누를 경우와 오른손으로 누를 경우 이동비용을 모두 처리한다. 처리 후 갱신! 동일한 값이 있을 수 있기 때문에 최솟값으로 넣어준다.

 

🤔 이동 비용은 어떻게 처리할까?
2차원 격자의 거리를 이용해 계산

$dx=∣x1−x2∣$ : 행간의 차이
$dy=∣y1−y2∣$ : 열간의 차이

1. 대각선 이동 비용
   $3 \times min(dx,dy)$
2. 상하좌우 이동 비용
   남은 행 이동: $dx-min(dx,dy)$
   남은 열 이동: $dy-min(dx,dy)$
   $2 \times (dx + dy - 2 \times min(dx,dy))$

따라서 두 합은
$$
2 \times (dx + dy) - min(dx,dy)
$$

⚠️ 코드짜면서 놓친 부분

1. 딕셔너리 key값에는 리스트를 사용할 수 없다.따라서, 튜플을 사용한다. key값은 해시가능해야하기때문에 불변셩이 있어야한다.
2. 딕셔너리의 get메서드key가 있으면 key값을 반환, 없으면 default 반환 dict.get(key,default)

💡 결과

---

def solution(numbers):
    key_pad = {
        '1': (0, 0), '2': (0, 1), '3': (0, 2),
        '4': (1, 0), '5': (1, 1), '6': (1, 2),
        '7': (2, 0), '8': (2, 1), '9': (2, 2),
        '0': (3, 1)
    }

    def cost(pos1, pos2):
        if pos1 == pos2:
            return 1
        x1,y1 = pos1
        x2,y2 = pos2
        dx,dy = abs(x1-x2),abs(y1-y2)
        if dx+dy == 1:
            return 2
        elif dx == 1 and dy == 1:
            return 3
        else:
            return 2*(dx+dy)-min(dx,dy)

    l_pos = key_pad['4']
    r_pos = key_pad['6']
    dp = {(l_pos, r_pos): 0}

    for number in numbers:
        new_dp = {}
        next_pos = key_pad[number]
        for (l_pos, r_pos), current in dp.items():
            if next_pos != r_pos: # 다음 숫자가 오른손에 있으면 안됨
                left_cost = current + cost(l_pos, next_pos)
                new_dp[(next_pos, r_pos)] = min(new_dp.get((next_pos, r_pos), float('inf')), left_cost)
            if next_pos != l_pos: # 다음 숫자가 왼손에 있으면 안됨
                right_cost = current + cost(r_pos, next_pos)
                new_dp[(l_pos, next_pos)] = min(new_dp.get((l_pos, next_pos), float('inf')), right_cost)
        dp = new_dp

    return min(dp.values())

💫 느낀점

---

모든 경우를 탐색할때 DP를 사용할 수 있다는 것을 알았고, 딕셔너리를 이용해 데이터를 효율적으로 저장할 수 있다는 것을 알게 되었다.

2차원에서 격자간의 거리를 계산하는 방법을 알게 되었다.

 

 그동안 너무 문제를 안풀었더니, 머리 회전이 안된다.. 오랜만에 알고리즘 정리해보면서 감을 찾아가야할것 같다.

그리고 티스토리에서 벨로그로 이동중이다. 벨로그가 가독성이 좋은듯? 하튼 포스팅좀 자주 하자구... 🥲

https://velog.io/@seoyoung7623

 

주소)

https://school.programmers.co.kr/learn/courses/30/lessons/136797

프로그래머스