[프로그래머스] 숫자 타자 대회

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

프로그래머스

1. 해설

너무 어려웠던 문제 ㅠㅠ.. 처음에는 그리디로 풀다가 며칠을 헤메었다. 그리디는 보통 input을 0부터 끝까지 훑는데 하다보니 그리디로는 풀리지 않고, 답을 numbers인덱스의 가장 마지막부터 훑어야 한다는걸 알았다. 즉 dp를 써야된다는 것

 

 

파이썬에서 재귀를 돌리다 런타임에러가 난다면 setrecursionlimit을 항상 설정해주자!

 

아이디어는 다음과 같다.

 

 

 

• 인풋이 두손가락에 이미 올라간 숫자라면 +1을 해주고 다음 상태로 넘어간다
• 이 조건이 필요한 이유는 두 손가락이 겹치지 않기 위해서이다. 이 조건이 없으면 이미 올라간 손가락에 다른손가락이 올라갈 수 도 있음

if next == left or next == right:
    dp[left][right][idx] = 1 + dfs(left,right,idx+1,numbers)
    return dp[left][right][idx]

 

• 인풋이 두손가락에 이미 올라간 숫자가 아니라면 왼손, 오른손을 움직이는 경우의 수에서 둘중 값이 작은거를 택한다

dp[left][right][idx] = min(
    distance[getDiff(left,next)] + dfs(next,right,idx+1,numbers),
    distance[getDiff(right,next)] + dfs(left,next,idx+1,numbers),
)

 

 

 

 

 

 

import sys
sys.setrecursionlimit(10**9)
dp = []

numMap = {
    0 : (3,1),
    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),
}

#y,x 순
distance = {
    (0,0) : 1,
    (0,1) : 2,
    (1,0) : 2,
    (1,1) : 3,
    (2,0) : 4,
    (0,2) : 4,
    (2,1) : 5,
    (1,2) : 5,
    (2,2) : 6,
    (3,0) : 6,
    (3,1) : 7,
}
dp = [[[-1 for _ in range(100001)] for _ in range(10)] for _ in range(10)]

def getDiff(A,B):
    numA = numMap[A]
    numB = numMap[B]
    return (abs(numA[0] - numB[0]), abs(numA[1]-numB[1]))

def dfs(left,right,idx,numbers):
    if len(numbers) == idx:
        return 0
    if dp[left][right][idx] != -1:
        return dp[left][right][idx]
    next = int(numbers[idx])
    #두 손가락이 겹치지 않기 위해서 아래 조건 필요
    if next == left or next == right:
        dp[left][right][idx] = 1 + dfs(left,right,idx+1,numbers)
        return dp[left][right][idx]
    dp[left][right][idx] = min(
        distance[getDiff(left,next)] + dfs(next,right,idx+1,numbers),
        distance[getDiff(right,next)] + dfs(left,next,idx+1,numbers),
    )
    
    
    return dp[left][right][idx]
    

def solution(numbers):
    
    answer = dfs(4,6,0,numbers)
    return answer