문제 : https://www.acmicpc.net/proble...

제 소스 : https://www.acmicpc.net/source... 

안녕하세요. 이 글을 읽고 계시는 여러분들의 도움이 필요한 한 학생입니다..

위의 문제에서 제가 나름 linear로 생각해낸 코드인데, 틀리다는 답을 받았네요..

나름 많은 경우의 수를 데이터로 입력해서 맞는 답이 떴기 때문에 맞을 거라 생각했는데.. 틀렸네요.

제가 고안한 알고리즘은 다음과 같습니다.

1. 맨 처음 n과 goalwins를 받고, goalwins를 퀵정렬으로 정렬합니다. (오름차순)

2. goalwins는 팀 1부터 팀 n까지의 목표 승리 횟수를 의미합니다. (goalwins[i] : i번째 팀의 목표 승리 횟수)

teamwins는 팀 1부터 팀 n까지의 현재 승리 횟수를 의미합니다. (teamwins[i] : i번째 팀의 현재 승리 횟수)

3. wins[x][y] 는 true일 경우 x가 패배자, y가 승리자가 됩니다. false일 경우 그 반대가 됩니다.

4. teamwins의 값들을 적당히 변경하다가 goalwins에 도달할 수 있게 될 경우 1을, 아닐 경우 -1을 출력하는 프로그램입니다.

5. teamwins의 초기 상태는 0승, 1승, 2승, ..., n-1승이 됩니다. 이에 따라 wins[x][x+k] (x>=0, k>0)은 true가 됩니다.

6. 맨 앞과 맨 뒷팀부터 천천히 중앙(head, tail)으로 이동하면서 goalwins와 teamwins를 비교하고, 값이 다르면 wins의 값을 반전시키면서 teamwins의 값을 변경시킵니다. (이긴팀, 진팀 횟수를 -1, +1 하면서 승패방향을 바꿈)

7. 그 과정에서 값을 바꾸는 게 불가능한 경우가 생기면 -1을 출력하면서 종료합니다.

8. 만약 head와 tail이 만나게 되면 상황에 따라 -1 또는 1을 출력합니다.

제가 고안한 알고리즘이 왜 정당하지 않은 지 여러 번 생각해봐도 잘 모르겠습니다.

읽어주셔서 감사합니다. 답변 기다리겠습니다.