저도 최근에 이문제 풀고 있었는대, 반갑습니다. ㅎㅎ
일단 SCC로 안하고, Backtracking으로 하시면, 아마도 이런 케이스 에서 오답이 나왔을 것 같습니다.
(정확히 확인해 본 것은 아니니, 참고만 하세요.
5 5
2 3 1 1 2
이런 입력에서, 제 예상에는 Backtracking으로 하면 4가 나올 것 같구요,
올바른 답은 5입니다.
ps : 저는 NCPC 2014 G번 24개 모두다 정답이 나왔는대도, 22%에서 '틀렸습니다' 나오네요. ㅎㅎ
BOJ에서, 따로 추가한 테스트 케이스가 있나보네요. ^^a
제가 푼 소스 링크 입니다. 참고하세요. https://bit.ly/352PZui
jiiw0n 3년 전
i번째 노드가 버스에 타려면 몇 명이나 필요한지를 `counts` 배열에 저장했습니다.
그리고 `counts`를 탐색하면서 `k`보다 작거나 같은 값이 나오면
백트래킹 하면서 `matched` 배열 값을 true로 바꿔주고 카운팅 했습니다.
`matched` 값이 true면 탐색하지 않았구요!
반례는 NCPC의 antigreedy 예제에서 틀렸더라고요.
틀린 건 확실하나 왜 이 방법으로 하면 틀리는 걸까요?
제 생각에는 `answer` 갱신하는 부분이 틀릴 수도 있는데
정확히는 잘 모르겠습니다.
제 코드의 문제점을 알려주시면 감사하겠습니다.