Coding Test/programmers
[프로그래머스] 숫자 타자 대회 (재귀)
Karla Ko
2023. 8. 28. 19:11
728x90
https://school.programmers.co.kr/learn/courses/30/lessons/136797
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
분석
2023.06.27 - [programmers/KAKAO] - 양과 늑대 (DFS)
양과 늑대 (DFS)
""" 2 ≤ info의 길이 ≤ 17 당신이 모은 양의 수보다 늑대의 수가 같거나 더 많아지면 바로 모든 양을 잡아먹어 버립니다. 당신은 중간에 양이 늑대에게 잡아먹히지 않도록 하면서 최대한 많은 수
karla.tistory.com
2023.07.03 - [programmers/KAKAO] - 사라지는 발판 (DFS)
사라지는 발판 (DFS)
https://school.programmers.co.kr/learn/courses/30/lessons/92345 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는
karla.tistory.com
풀이
import sys, math
sys.setrecursionlimit(200000)
from collections import defaultdict
cache = defaultdict(dict)
W = [
[1, 7, 6, 7, 5, 4, 5, 3, 2, 3], # 0
[7, 1, 2, 4, 2, 3, 5, 4, 5, 6], # 1
[6, 2, 1, 2, 3, 2, 3, 5, 4, 5], # 2
[7, 4, 2, 1, 5, 3, 2, 6, 5, 4], # 3
[5, 2, 3, 5, 1, 2, 4, 2, 3, 5], # 4
[4, 3, 2, 3, 2, 1, 2, 3, 2, 3], # 5
[5, 5, 3, 2, 4, 2, 1, 5, 3, 2], # 6
[3, 4, 5, 6, 2, 3, 5, 1, 2, 4], # 7
[2, 5, 4, 5, 3, 2, 3, 2, 1, 2], # 8
[3, 6, 5, 4, 5, 3, 2, 4, 2, 1], # 9
] # W[i][j] : i번째 숫자에서 j번째 숫자로 이동하여 누를 때의 가중치
def solution(numbers):
def solve(i, left, right):
if i==len(numbers):
return 0
if (left, right) in cache[i]:
return cache[i][(left, right)]
w=math.inf
num=numbers[i]
if num!=left: # 오른손 이동
w=min(w, solve(i+1,num,left)+W[right][num])
if num!=right: # 왼손 이동
w=min(w, solve(i+1,num,right)+W[left][num])
cache[i][(left, right)] = w
return w
numbers = list(int(x) for x in numbers)
return solve(0,4,6) # 최소한의 시간으로 타이핑을 하는 경우의 가중치 합
728x90