문제 출처 : https://school.programmers.co.kr/learn/courses/30/lessons/42860
아이디어
Greedy라는 아이디어를 가지고 시작했지만 한 번 생각해보자.
두 가지 방식으로 조이스틱을 움직이게 된다.
1. A가 아닌 알파벳에서 Alphabet-"A"
2. String 이동 횟수
1번의 경우는 고정적이므로 고민하지 않아도 된다. 따라서 Optimal한 해를 구하기 위해서는 어떤 방식으로 조이스틱을 움직일지 2번을 고민해야 한다.
움직임에 대한 규칙을 정하기 위해 A는 있으나마나한 알파벳이므로 이를 고려해 기준을 만들어보고자 했다.
최소값을 구하기 위한 어떤 방식이 떠오르지 않기에 A가 아닌 알파벳( nA )에서 발생하는 각각의 path의 cost 중 가장 작은 값을 구하면 될 것 같다.
모든 nA를 원소로 가지는 리스트에서
for n in len(nA) :
n'st nA -> (n-1)' nA #길이 생성위와 같이 모든 경우에 대한 길이를 생성하고 조이스틱 움직임은 1. 처음부터 쭉 직진만 하는 경우 2. 너무 긴 A를 만나는 경우 되돌아가는 경우 이렇게 두 가지로 발생하므로 아래 두 방식으로 계산했으나 사실 여기에는 세 번째 방식이 존재했다.
왜 세 번째 그림은 생각하지 못했을까?? 좌측에서 우측으로 가는 일반적인 사고 체계로 인해 [ n -> n-1 ]의 박스에 대해 왼, 오 방향밖에 생각해내지 못했다. General하게, 공평하게 알고리즘의 적용.
세상은 너무나도 커