강의로 돌아가기
강성민

중요한 힌트 정리해드립니다.

  1. 어떤 지점의 목표가 A 가 아니라면, 그 지점은 반드시 방문해야 한다. 즉 A인 위치는 무시할 수도 있다.

  2. 1의 이유에 의해서 조이스틱을 상하로 움직이는 횟수는 정해져있다. 이는 최적화 대상이 아니다.

  3. 따라서 최적화 해야 할 것은 조이스틱을 좌우로 움직이는 횟수이고, 이것의 최대값은 한쪽 방향으로 계속 움직였을 경우인 name.length-1이다.

  4. 1에 의해서 1개 이상의 A가 연속적으로 배치되어있는 경우, 이 구간중 한 구간을 방문하지 않고도 단어를 만들 수 있다. 두 개 이상의 구간을 방문하지 않는 것은 방문하지 않는 구간들 사이에 A가 아닌 단어가 존재하게되므로 불가능하다.

  5. 따라서 조이스틱 좌우 횟수의 최소값은, name.length-1 과 연속적인 A 한 구간을 제외하고 나머지 구간을 최소 횟수로 전부 방문했을 때의 값들 중 최소값이다.

0 개의 답변
답변 쓰기
이 입력폼은 마크다운 문법을 지원합니다.