https://www.acmicpc.net/problem/13560

Baekjoon Online JudgeBaekjoon Online Judgewww.acmicpc.net


어찌저찌 코드를 짰는데.. 블로그나 다른 곳 풀이 참고해보면 다들 내 풀이랑 너무 달라서 별 도움이 안 되더라고

게시판 반례나 이런 건 또 다 통과하는데 1% 틀림당하니까 좀 오기가 생겨서 로직에 어느 부분이 잘못된 건지라도 알고 싶음


아래는 내 풀이

http://boj.kr/c337cd759c034c94a082445b1a75b0cc

Baekjoon Online JudgeBaekjoon Online Judgeboj.kr



처음에 접근할 때는 예제를 좀 그려봤었는데

0 ~ N - 1번까지의 팀이 있을 때, i번째 행의 팀이 j번째 열의 팀과 경기했을 때 이겼으면 1, 졌으면 0 이런 식으로 표기해서

일종의 경기 행렬? 비스무리한 걸로 나타내보고자 했었음.


올바르지 않은 경기 결과면 테이블을 하나하나 채우다가 중간에 터지니까 테이블이 다 완성되면 올바른 걸로 판단

각 행의 원소 합을 나타낸 배열이 원래 입력이랑 같은 집합이면 되니까

입력받은 점수를 내림차순으로 정렬하고 테이블을 하나하나 채움.


예를 들어 입력이

10

2 2 2 3 4 4 4 8 8 8이면 정렬된 값이 8 8 8 4 4 4 3 2 2 2니까




8을 위쪽 삼각형 부분에 채움

그러면 A팀은 점수가 8이 되고 임의로 B ~ I팀과 경기했을 때는 이겼고, J팀은 졌다고 둔 다음에

아래쪽 삼각형 부분을 아까 채운 결과에 위배되지 않게 숫자를 반전해서 집어넣음


위쪽 삼각형 부분은 한 번 채우면 다시 건드릴 일 없으니까 filled 배열로 여기 넣은 적 있는지 확인해주고

아래쪽 삼각형 부분은 이전까지 채운 값에 의거해서 지금까지 이겼어야 할 팀 수(= 이미 가지고 있는 점수)를 vld 배열에 집어넣어서 관리함




대충 이런 식으로 생각하니까 위쪽 삼각형 부분은 채워넣을 부분(남은 부분), 아래쪽 삼각형 부분은 이미 결과가 결정난 부분이라고 판단해서

점수들을 집어넣을 때 집어넣을 점수 - 해당 행의 vld 배열 값이 위쪽 삼각형 부분의 크기 이하일 때 넣음




이런 식으로 하면 아까 말한 입력에서는

3번째 8을 넣을 때만 유일하게 못 집어넣고 나머지를 전부 넣고 맨 끝쪽 행만 남게 되는데

삽입하지 못한 점수를 R 배열에 따로 두고 점수들의 삽입이 일차적으로 끝난 다음에 자리를 재분배했음


만약에 위쪽 삼각형 부분이 충분했다면 진작에 삽입되었을 거지만 못 그랬으니까

삽입 못하고 남은 값은 아직 비어있는 행들 중에 vld 값으로 이미 그만큼을 채운 값에 분배하도록 처리하려고 했음

그러면 테이블을 다 채울 수 있으니까 유효한 점수들이라 판단함


이러면 

2

0 0

같은 경우에서도 1 출력하길래 점수 합이 n * (n - 1) / 2랑 같은지 확인하는 부분도 따로 넣으니까

다른 반례들 다 통과하던데 왜 안되는지 모르겠다...


장문 미안ㅠㅠ 읽어줘서 고맙다 잘못된 부분 있으면 알려줘