godgod3260   5년 전

안녕하세요, 이번에 1021번 문제를 풀다가 틀려서 반례를 찾아보던 도중 이상한점을 발견하여 질문올립니다.

반례를 찾던 도중 정답자분들의 반례를 볼 수 있었습니다.

그 중 하나의 반례는

9 5

5 1 4 2 3 

이고, 정답은 12라고 하였습니다.

하지만 제가생각했을 때 정답은 6입니다. 그 이유는

1번째 연산은 횟수에 상관없고, 2번연산과 3번연산만 최솟값을 구하는 것이기 때문입니다. 

처음 큐에는 

[ 1 2 3 4 5 6 7 8 9 ] 가 저장되어있을 것입니다.

[ 5 ] 를 찾아야하기 때문에 [ 1 2 3 4 ] 를 4번의 2번연산을 통해 뒤로 빼줍니다.

[ 5 6 7 8 1 2 3 4 ] 가 큐에 저장이 되고, 5를 1번연산을 통해 제거합니다. 그러면 2번연산이 총 4번 사용된 것을 확인할 수 있습니다.

그 후, [ 6 7 8 1 2 3 4 ] 가 큐에 남아있습니다.

[ 6 ] 은  찾고자하는 { 5 1 4 2 3 } 에 포함되지않기때문에 1번연산으로 제거해줍니다. 물론, 2/3번연산의 횟수는 증가되지않습니다.

그런식으로 [ 6 7 8 ]을 1변연산을 통해 제거해줍니다.

그러면 큐에는 [ 1 2 3 4 ] 가 남고 2/3번 연산은 아직 4번만 사용한 것입니다. 찾고자하는 순번은 이제 { 1 4 2 3 }이 남아있고

큐의 맨 첫번째 값은 [ 1 ] 이므로 1번연산을 통해 제거하면 찾고자 하는 값은 { 4 2 3 } 만 남게되고 

큐에는 [ 2 3 4 ]가 남아있습니다.

3번연산을통해 [ 4 2 3 ] 으로 만든 후, 1번연산을 해줍니다. 그러면 2/3번연산의 횟수는 총 5번이 됩니다.

찾고자 하는 값은 { 2 3 } 이 남았는데 순서대로 1번연산을 해주면 원하는 값을 찾을 수 있습니다.

따라서, 답은 5가 맞는것이 아닌가하는 생각에 질문올립니다.!!

( 제가 문제를 제대로 이해하지못하고 이런 의견을 낸 것일 수도 있습니다.. )

djm03178   5년 전

"[ 6 ] 은  찾고자하는 { 5 1 4 2 3 } 에 포함되지않기때문에 1번연산으로 제거해줍니다. 물론, 2/3번연산의 횟수는 증가되지않습니다."

이 부분이 잘못되었습니다. 찾으려고 하는 수가 아닌 것은 뽑지 않아야 합니다.

godgod3260   5년 전

감사합니다. 제가 문제를 제대로이해하지못한것같습니다 ㅠㅜ

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