우선 p를 구하실때 S가 아니라 K랑 비교하다보니 제대로된 위치를 찾지 못합니다.
예제에서는 첫번째 K와 S가 우연히 같아서 값이 동일했고 두번째는 0이다 보니, 예외처리로 P를 구하는 거라 제대로 답이 잘 나온것 같습니다.
반례로
3 6 4
0 1
2 2
5 1
하면 첫번째 예시의 답과 같이 10이 나와야하지만 올리신 코드는 2를 출력합니다.
2513번 - 통학버스
우선 p를 구하실때 S가 아니라 K랑 비교하다보니 제대로된 위치를 찾지 못합니다.
예제에서는 첫번째 K와 S가 우연히 같아서 값이 동일했고 두번째는 0이다 보니, 예외처리로 P를 구하는 거라 제대로 답이 잘 나온것 같습니다.
반례로
3 6 4
0 1
2 2
5 1
하면 첫번째 예시의 답과 같이 10이 나와야하지만 올리신 코드는 2를 출력합니다.
어... 약간 로직을 복잡하게 구현해 놓아서 직관적으로 보이는 부분만 지적해드립니다..
1. 학교 오른쪽 if(cnt < 1) 부분은 아마, 벡터 인덱스에서 -1이 되지 않도록 처리하는 코드 같은데, 그러면 cnt < 0이 되어야할 것 같습니다.
2. 학교 왼쪽 에서는 cnt == p+1로 처리해놓고, 학교 오른쪽은 cnt == -1로 처리해놓으셨는데, 그러면 왼쪽에 모든 v[cnt].second가 0이여야한다는 보장이 있어야 합니다. 근데, 그렇지 않다보니 오른쪽에서도 중복해서 계산할 가능성이 있습니다. 첫번째 예제 에서도 사실 중복해서 계산해야하지만 flag조건으로 탈출하다 보니 성공한 것 처럼 보인것 같습니다.
로직은 잘 생각하셨어서 특수한 상황을 고려해보거나, 일반적인 상황에서 내가 생각한대로 진행이 잘 되고 있는지, 변수에 내가 생각한 값이 담기는지 디버깅해보시면서 실력을 길러보시면 좋을 것 같아요.
1번은 작성자 분이 하신 말씀이 맞는것 같습니다.
2번을 설명하기 앞서 flag조건은 최대 탐색할 인덱스까지 탐색했을 때 탐색을 멈추는 일을 작동한다고 생각하겠습니다.
그러면 우선 오른쪽을 탐색하기 전에 flag = 0으로 다시 초기화 해놓아야합니다. 이 코드에서 flag = 0을 cnt = n-1위에 작성했다고 가정하겠습니다.
(가정하지 않았을 때 아래 testcase를 넣어보셔도 잘못된 답이 나옵니다.)
2번의 요지는 학교 왼쪽을 구할 때는 학교의 상대적 기준(p기준) 왼쪽만 탐색을 진행하였는데, 오른쪽은 cnt == -1이다 보니 모든 경우를 다 탐색하게 됩니다.
그러면 왼쪽에서 탐색했던 부분도 다시 탐색하게 될텐데, 이미 탐색을 진행했기에 그 경우에는 어떠한 값도 더해지면 안됩니다.
만약 모든 경우를 볼때는 왼쪽에서 처리할 때 학생수를 반영했다면 v[cnt].second를 모두 0으로 처리해주는 작업이 정확하게 이루어 져야합니다.
따라서 오류가 발생하게 됩니다.
반례로
4 3 18
10 4
12 3
16 2
20 4
ans : 52
flag = 0 반영 x -> 작성자 코드 : 48
flag = 0 반영 o -> 작성자 코드 : 40
확인해보고 싶으시면 오른쪽 탐방코드에서 ans를 직접 찍어보시면 좋을 것 같습니다.
댓글을 작성하려면 로그인해야 합니다.
brady0116 1년 전
계속 수정해도 2%에서 틀리네요.
초등학생인데 제발 도와주세요 ㅠㅠ