jiiw0n   3년 전

i번째 노드가 버스에 타려면 몇 명이나 필요한지를 `counts` 배열에 저장했습니다.

그리고 `counts`를 탐색하면서 `k`보다 작거나 같은 값이 나오면 

백트래킹 하면서 `matched` 배열 값을 true로 바꿔주고 카운팅 했습니다. 

`matched` 값이 true면 탐색하지 않았구요! 

반례는 NCPC의 antigreedy 예제에서 틀렸더라고요. 

틀린 건 확실하나 왜 이 방법으로 하면 틀리는 걸까요? 

제 생각에는 `answer` 갱신하는 부분이 틀릴 수도 있는데 

정확히는 잘 모르겠습니다. 

제 코드의 문제점을 알려주시면 감사하겠습니다. 

저도 최근에 이문제 풀고 있었는대, 반갑습니다. ㅎㅎ

일단 SCC로 안하고, Backtracking으로 하시면, 아마도 이런 케이스 에서 오답이 나왔을 것 같습니다.

(정확히 확인해 본 것은 아니니, 참고만 하세요.

5 5

2 3 1 1 2

이런 입력에서, 제 예상에는 Backtracking으로 하면 4가 나올 것 같구요,

올바른 답은 5입니다.

ps : 저는 NCPC 2014 G번 24개 모두다 정답이 나왔는대도, 22%에서 '틀렸습니다' 나오네요. ㅎㅎ

BOJ에서, 따로 추가한 테스트 케이스가 있나보네요. ^^a

제가 푼 소스 링크 입니다. 참고하세요. https://bit.ly/352PZui

댓글을 작성하려면 로그인해야 합니다.