cuhcuh1   8달 전

일단 코드에 대한 설명을 하자면,

주어진 랜선의 모든 길이의 합을 sum에 넣고, 만들고자 하는 랜선으로 나누면 가능한 최대의 랜선 길이가 나오게 됩니다.

그리고 while 안에서 랜선길이를 변화시켜가면서 그때의 숫자를 세어, 원하는 숫자가 나오면 반복문을 나오는 형태로 짰습니다.

dist는 각각의 랜선 길이로 나누면 몫은 사용할 수 있는 랜선이고, 나머지는 사용할 수 없는 랜선이 되므로

이때 나머지가 가장 큰 랜선을 기준으로 거기에 하나를 더 사용할 수 있게 길이를 조정한 후 계속적으로 반복되는 형태입니다.

임의로 테스트 케이스를 넣어 보고, 질문란에 올라와있는 테스트 케이스를 넣어봤는데도 계속 틀렸다고 나와서

어디가 잘못 됬는지 잘 모르겠습니다. 푸는 방법 자체가 잘못된 걸까요?? ㅜ

도움을 구합니다 ㅠㅠ

waninoko   8달 전

이분법을 사용하셔야 풀 수 있는 문제입니다

cuhcuh1   8달 전

분류에도 이분법으로 되어있어서 이분법으로 푸는 것은 알고있습니다.

처음에 문제를 보자마자 떠오른 방법대로 한번 풀어봤는데 안되서 고민중에 있는 겁니다 ㅠ

논리가 안맞거나 잘못된 부분을 가르쳐주셨으면 좋겠습니다. ㅠㅠ

f52985   8달 전

의도한 방법은, "만약 원하는 개수만큼의 랜선을 만들기에 현재 dist 값이 너무 길면, 만들 수 있는 랜선의 개수가 적어도 하나 늘어날 수 있는, 최대의 dist값을 찾는 것을 계속 반복한다" 인 것 같은데요,

다만, "나머지가 가장 큰 랜선을 기준으로" 길이를 줄이는 것은 의도했던 동작을 하지 않을 수 있습니다.

간단한 예를 들어, 처음 주어진 두 랜선의 길이가 각각 4,10이고, 이로부터 2개의 랜선을 만들고 싶다고 해봅시다.

이로부터 처음 dist값을 구해보면 14/2=7 이 됩니다.
그러면 4짜리 랜선의 남은 길이는 4, 10짜리 랜선의 남은 길이는 3이 되겠죠.

여기서 나머지가 큰쪽인 4를 기준으로 하면 다음 dist값은 4/(0+1)=4가 될 것입니다.
하지만 원래는 dist값을 10/(1+1)=5로 잡는 것이 조건을 만족시키는 올바른 dist값이 될 것입니다.

제 생각으로는 다음 dist값을 결정하기 위해서는 나머지 뿐만 아니라 몫도 고려를 해야할 것이라고 생각하지만, 정확히 계산하는 게 쉽진 않을 것 같네요.


그리고 시간 복잡도를 생각해 보면, 이분법보다는 비효율적인 방법이 될 것 같네요..

제시된 방법은 dist를 최소 1씩 줄여나가기 때문에 O(dist)까지 갈 수 있지만, 이분법은 항상 절반은 줄이므로 O(log dist)가 되니까요.

plzrun   8달 전

dist가 0이될 때도 고려해주세요. 분모값으로 0이 들어가는 경우도 생기는거 같은데요.

f52985   8달 전

plzrun

dist가 0이 될 수는 없습니다.

dist가 0이 되려면 맨 처음 계산할 때 sum<need이거나, dist=1인 상태에서 for문으로 넘어가는 경우 밖에는 없는데요, 

양쪽 모두 필요한 랜선은 반드시 확보할 수 있다는 문제의 조건에 의해 불가능합니다.

plzrun   8달 전

아 그렇군요

그런 경우는 입력으로 안들어오네요 ㅎ;; 죄송 ㅎ

cuhcuh1   8달 전

감사합니다! 뭐가 문제인지 이제 좀 감이 잡히네요!

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