백준 - ⚾

문제 출처: https://www.acmicpc.net/problem/17281

17281번: ⚾

 

 

고민의 흔적↓↓

 

 

이번 문제는 순열 + 구현 느낌의 문제였다.

"가장 많은 득점을 하는 타순을 찾고, 그때의 득점을 구해보자." 이 문장을 보고 순열을 이용해야 겠다는 생각을 하게 되었다.

우선, 순열을 통해 타순을 정하고 나면 그 타순대로 진행하면 된다. 점수를 얻는 방식은 3 크기의 BOOLEAN형 배열을 사용하였다.

 

 

안타, 2루타, 3루타 일 경우,

3 크기 배열의 역순 탐색을 통해 해당 칸이 false이면 아직 해당 루에 아무도 없다는 것을 의미한다. 만약 true이면 현재 타자가 친 만큼 이동하여 true로 체크해주면 된다.(기존은 false로 다시 설정).

 

홈런일 경우,

true로 체크된 개수만큼 점수를 올려주고, 홈런을 친 타자도 포함해야 하므로 +1 해준다.

 

아웃일 경우,

아웃 카운트를 하다가 3 아웃이 될 경우, 배열은 전부 false로 초기화된다.

 

 

여기까지 푸는 순간 됐다!라고 생각했다.

하지만 시간 초과가 발생했다..

 

찾아보고 찾아보다 결국 해결책은 순열의 범위가 너무 커서 초과 난 거라 판단하였다. 지문에서 1번 선수가 무조건 4번 타자로 고정되어있으므로 모든 순열이 아니라 4번째가 1번 선수인 경우만 확인하면 된다.

 

 

 

물론 코드만 보면 이해가 안 갔다. 결국 엑셀을 사용하 매 경우의 수마다 확인해보기로 했다.

 

대충 요렇게..