[Programmers] 숫자 타자 대회

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/136797

프로그래머스

 

numbers의 길이가 최대 십만이기 때문에 브루트 포스로 풀 수 없는 문제였습니다.

따라서, 저는 오랜만에 DP로 접근해서 풀었습니다.

 

알고리즘은 아래와 같습니다.

1. 숫자는 0 ~ 9로 한정되어있기 때문에 이차원 배열을 통해 최소 가중치를 미리 구해줍니다.

2. [numbers의 최대 길이][왼손이 누를 수 있는 0~9까지의 숫자][오른손이 누를 수 있는 0~9까지의 숫자] 와 같이 3차원 DP 배열을 선언하고 아래와 같은 로직으로 전개합니다.

2.1 왼손가락 혹은 오른손가락이 현재 눌러야할 숫자에 올라가 있으면 가중치 1을 더한 상태로 다음 숫자로 넘어갑니다.

2.2 왼손가락이 움직이거나 오른손가락을 움직입니다. 이때, 둘 중 더 적은 가중치의 합을 반환해야 하므로 두 케이스 중 최소인 가중치를 반환합니다.

 

주의: 재귀함수의 매개변수로 numbers를 넘길 경우 시간 초과가 발생하므로 전역 변수로 numbers를 복사한 상태로 사용하는 것을 권고합니다. 

 

 

개발환경: Programmers IDE

 

지적, 조언, 질문 환영합니다! 질문 남겨주세요~