C개보다 많이 설치해서 나올 수 있는 답이 x라면 C개만 설치해서 x보다 더 나쁘지는 않은 답을 항상 구할 수 있습니다. 그러니까 이분 탐색이 되는 것입니다.

위 코드는 이런 데이터에서 답이 제대로 나오지 않습니다.

일반적으로 문제나 데이터가 잘못된 경우보다는, 본인의 코드가 잘못된 경우가 훨신 많습니다.

문제가 잘못된 것이 확실한 상황이 아니면, 질문탭에 먼저 글을 올리시는게 더 좋을 것 같습니다.

Green55님 에러코드의 예외를 찾아 주셔서 감사합니다^^

그런데, 위의 에러코드와 별개로 제가 지적한 건 문제의 표현이 애매하다라는 것입니다. 다시 얘기하자면, 

예외가 발생하는 경우또한 처음에 지정한 c보다 그 이상이되는 부분에서 발생한 것 아니겠습니다(Green55님이 지적해주신)

그러니까 "c개를 설치해서" 라는 표현을 "c개 이상을 설치해서"라는 표현으로 바꾸어야 문제의 정확성이 올라갈 거 같다는 얘기입니다. 문제자체에는 그 어디에도 c개이상을 설치해서 나온 값이 답이 될수 있는 표현이 없습니다. 

djm03178이 얘기하신게 맞습니다. 그러나 문제에서는 "c개의 공유기를 n개의 집에 적당히 설치해서~~"라는 표현을 사용하였습니다.

djm03178의 "C개보다 많이 설치해서 나올 수 있는 답이 x라면 C개만 설치해서 x보다 더 나쁘지는 않은 답을 항상 구할 수 있습니다." 라는 건 문제를 풀면서

유추된 사실이지, 질문자체에는 존재하지 않는 표현입니다. 무엇보다도 결국 문제 자체에 나온표현은 "C개의 공유기를 설치해서~~"라고 나왔기 때문에(C개로 확정지었기 때문에)질문을 하게 되었습니다.

다시 말하자면, "C개의 공유기를 " 이라는 표현대신 "C개 이상의 공유기를"이라는 표현으로 바꾸어야 한다는게 저의 주장입니다

답변을 잘못 이해하신 것 같습니다. 한 문장으로 정리해서 말씀드리자면, "C개 설치헀을 때의 답"과 "C개 이상을 설치했을 때의 답"이 같습니다. 그러므로 지문을 C개로 하든, C개 이상으로 하든 아무런 지장이 없고, 지문을 바꾸어야만 할 정당한 이유도 되지 않습니다.

좀 더 구체적인 예시를 들어서 설명드리자면, 지문을 "C개 이상"으로 바꾸어서 풀었을 때 C+1개를 설치해서 x개를 구하는 것이 답이라고 구했다고 합시다. 그러면 무조건 C개를 설치하게 했을 때의 답은 무엇일까요? 정답은 x입니다. 그 이유는 C+1개를 설치했을 때의 최적의 답이 C개를 설치했을 때의 최적의 답보다 좋을 수가 없기 때문입니다. 그러므로 "C개"로 하든, "C개 이상"으로 하든 어떤 입력에 대해서도 항상 같은 답이 도출될 수밖에 없다는 것이고, 따라서 지문을 바꿔야 할 이유도 전혀 없다고 말씀드리는 것입니다.

"C개 이상의 공유기를 설치했을 때 최대 거리를 출력하는 코드"가 정답인 이유는,

논리적으로 "C개 이상의 공유기를 설치했을 때 최대 거리"와 "C개의 공유기를 설치했을 때 최대 거리"가 같기 때문입니다.

만약 "C개의 공유기를 설치했을 때 최대 거리를 출력하는 코드"를 제출하신다면, 정답이 나옵니다.

작성자님이 틀리신 이유는, C개의 공유기를 설치했을 때 최대 거리를 출력하지 못하기 때문입니다.

그리고 Green55님이 찾아주신 반례는 이 코드가 C개만을 설치했기 때문에 틀렸다는 걸 보여주는 게 아니고 C개만을 설치하는 코드를 잘못 짰기 때문에 틀렸다는 것을 보여주신 겁니다. C개만을 설치하는 코드를 제대로 짜면 당연히 맞습니다. C개 이상을 설치하셨다는 코드는 C개를 넘게 설치하는 것과는 무관하게 C개를 설치하는 모든 경우를 제대로 탐색하기 때문에 맞는 것입니다.

1. 두 분이 공통으로 지적하신 것은 "C개 이상의 공유기를 설치했을 때 최대 거리"와 "C개의 공유기를 설치했을 때 최대 거리"가 같다"라는 것인데, 결과가 같다고 두 표현이 지니는 포함관계가 같은 건 아닙니다. 'C개' 와 'C개 이상' 이 가지는 언어적인 범위의 차이는 두 분다 아실거라 생각됩니다.

2. djm03178님이 지속적으로 언급하고 있는 부분은 무슨 의미인지 파악하고 있습니다. 하지만 위의 4 3 '/n' 1 4 7 10을 예로 들어보면 c=3인데 결국 4개설치했을 때가 최적의 답이 되지 않습니까! 그렇기 때문에 c개 이상을 바꾸어야 합니다

3. 저의 주장은 "c개"를 설치했을때, 도출되는 답이 사실은 "c개이상"을 설치했을때를 의미한다는 것입니다.

4. 그리고 c개이상일 때와 c개일때의 답은 같아서는 안됩니다. 논리적으로 c개이상일때는 c개를 포함하고도 기타의 영역이 존재하기때문입니다. 즉, 두분이서 생각하고 있는 c개는 사실, c개이상을 의미하고 있는 것입니다. 이 부분에 대해서 djm03178님은 c개이상이라하더라도 결국 c개일때가 최적의 답이다 라고 주장하시는것인데,(저도 그렇게 생각했습니다) 그런데 green님이 들어주신 반례가 그게 아니라는 것을 보여주고 있는 것같습니다.(c개를 제외한 c개 이상인 경우가 답이 되는 case)

djm03178님의 주장이 맞다면 결국, 모든 경우는 count == c인 경우에 수렴해야 하는데, 그게 아니므로 오류가 나고 있는 것같습니다 //물론, 제 코드가 잘못작성되었다면 별개의 문제지만...

무턱대고 글을 쓰는것이 아님을 언급하고 싶습니다. 두 분께서 생각하시는 "c개"는 사실은 "c개 이상"을 의미하고 있는 것입니다.

+djm03178님이 마지막에 주장하신 "c개를 설치하는 모든 경우"는 사실은 "c개 이상을 설치하는 모든 경우"입니다. 그러므로 c개이상이 맞는 표현인 것 같습니다

PS. 혹시 여유가 되신다면 두분이 작성한 코드를 보여주실수 있으시겠습니까! 보여주신다면, 얘기가 길어지지 않을 것 같습니다.

"하지만 위의 4 3 '/n' 1 4 7 10을 예로 들어보면 c=3인데 결국 4개설치했을 때가 최적의 답이 되지 않습니까! 그렇기 때문에 c개 이상을 바꾸어야 합니다"

이 부분이 틀렸다는 것입니다. 왜 4개를 놓을 때가 최적의 답인가요? 3개를 놓아도, 4개를 놓아도 가장 인접한 공유기 사이의 최대 거리는 3으로 만드는 것이 최적입니다.

이렇게 되지 않는 반례를 하나 찾아내신다면 C개 이상으로 하는 것이 맞겠지만, 저는 이미 왜 C개일 때의 답을 구하는 코드가 C개 이상일 때의 답을 구하는 문제에서도 답을 내는지를 설명드렸습니다.

3개를 놓아도 '1' '4' '7' 10 으로 해서 가장 인접한 공유기 사이의 거리의 최댓값은 3이고, 4개를 놓아도 '1' '4' '7' '10' 으로 역시 가장 인접한 공유기 사이의 거리의 최댓값은 3입니다. 어느 부분이 'C개 이상으로 해야만 답이 나온다'는 것인가요?

코드를 보여드린다고 해도 설득하는 데에는 도움이 되지 않을 것 같습니다. 왜냐하면 제 코드도 cnt >= c라고 쓰고 있기 때문이죠. 하지만 이건 계속 말씀드렸듯이 C개를 설치할 때의 답과 C개 이상을 설치할 때의 답이 같기 때문에 이렇게 해도 되기 때문인 것이고, 그렇기 때문에 이분 탐색이 성립하여 그런 방식으로 풀 수 있기 때문일 뿐, 절대로 문제가 C개 이상일 때를 요구해서가 아닙니다.

10을 무조건  두어야 한다는 저의 집착이었네요~ .. 감사합니다!!! 명확히 이해했습니다.

이 문제는 "정확히 c개"를 설치하는 문제입니다. 이렇게 구한 최적해를 A라고 합시다. 한편, 질문자님은 "c개 이상"을 설치하셨습니다. 이렇게 구한 최적해를 B라고 합시다. 그러면,

1. B를 출력하면 정답을 받습니다.

2. A와 B는 같습니다.

3. 따라서 A를 출력하면 정답을 받습니다.

3번이 이해되지 않으신다면 https://www.acmicpc.net/blog/v... 을 읽어보시기 바랍니다.

그 사이에 댓글이 하나 더 달렸군요.