dotorya   1년 전

저는 이 문제가 N*(N-1)/2가지의 합이 임의의 순서대로 뒤섞여 주어지는 줄 알아서 백트래킹을 돌려서 짰는데, 다른 분들 소스코드를 보니 a1+a2, a1+a3, ... , a_n-1 + a_n처럼 순서대로 주어지는것 같습니다.

혹시 문제의 입력이 저렇게 순서대로 주어지는 게 맞나요?

pichulia   1년 전

아니요. 그렇지 않습니다.

주어진 n*(n-1)/2개의 수열을 크기 순으로 정렬했을 때

가장 작은 숫자는 원래 수열에서 몇번째로 작은 숫자끼리 더해져서 만들어진걸까요?

가장 작은 숫자 2개 (a1 + a2)의 합일 것입니다.

마찬가지 이유로 두번째로 작은 숫자는 a1+a3이 되겠고요..

비슷한 논리로 가장 큰 숫자와 두번째로 큰 숫자가 어떤 수로 이루어져 있는지도 알게 됩니다.


이제 세번째로 작은 숫자가 a1+a4인지 a2+a3인지 판단하는 일이 남았네요. 이 이후는 이제 백트래킹으로 푸는 문제입니다.

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