brady0116   1년 전

계속 수정해도 2%에서 틀리네요.

초등학생인데 제발 도와주세요 ㅠㅠ

keyboardmunji   1년 전


우선 p를 구하실때 S가 아니라 K랑 비교하다보니 제대로된 위치를 찾지 못합니다.

예제에서는 첫번째 K와 S가 우연히 같아서 값이 동일했고 두번째는 0이다 보니, 예외처리로 P를 구하는 거라 제대로 답이 잘 나온것 같습니다.

반례로 

3 6 4

0 1

2 2

5 1

하면 첫번째 예시의 답과 같이 10이 나와야하지만 올리신 코드는 2를 출력합니다.

brady0116   1년 전

앗 실수했네요 ㅠㅠ

 답변 감사합니다 ~!!!!

brady0116   1년 전

그래서 아래 코드로 바꿨는데 여전히 2%에서 틀리네요. 뭐가 문제일까요?

keyboardmunji   1년 전

어... 약간 로직을 복잡하게 구현해 놓아서 직관적으로 보이는 부분만 지적해드립니다..

1. 학교 오른쪽 if(cnt < 1) 부분은 아마, 벡터 인덱스에서 -1이 되지 않도록 처리하는 코드 같은데, 그러면 cnt < 0이 되어야할 것 같습니다.

2. 학교 왼쪽 에서는 cnt == p+1로 처리해놓고, 학교 오른쪽은 cnt == -1로 처리해놓으셨는데, 그러면 왼쪽에 모든 v[cnt].second가 0이여야한다는 보장이 있어야 합니다. 근데, 그렇지 않다보니 오른쪽에서도 중복해서 계산할 가능성이 있습니다. 첫번째 예제 에서도 사실 중복해서 계산해야하지만 flag조건으로 탈출하다 보니 성공한 것 처럼 보인것 같습니다.

로직은 잘 생각하셨어서 특수한 상황을 고려해보거나, 일반적인 상황에서 내가 생각한대로 진행이 잘 되고 있는지, 변수에 내가 생각한 값이 담기는지 디버깅해보시면서 실력을 길러보시면 좋을 것 같아요.

brady0116   1년 전

1) cnt<1이면 다음 동작인 cnt--에서 cnt가 음수가 될까봐 일부로 그렇게 한 겁니다.

2) 잘 이해가 안 되네요. 자세한 설명 부탁드립니다.

keyboardmunji   1년 전

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년 전

덕분에 맞았습니다!!!!!

너무너무 감사드립니다!!

(실수를 많이 했네요)

답변 빨리 해주신 점 감사합니다!!

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