N개의 수들 중에서 2개를 선택하는 경우의 수는 NC2 = N(N-1)/2 인데, N개의 수들 중 2개를 선택해서 더한 N(N-1)/2개의 합이 주어지면 원래 N개의 수를 구하는 문제이다.
예제를 손으로 풀어보면 a+b=1269, b+c=1160, c+a=1663 으로 놓으면.. 변수는 3개, 식도 3개.. 이렇게 되면 a, b, c는 다 구할 수 있다. 계속해서 양 변을 다 더하면 2(a+b+c)=4092 가 되고, a+b+c=2046을 알 수 있고 계산해보면 a, b, c 각 값을 구할 수 있다. 근데 문제는 N이 최대 100이라는 것이다. 그럼 100*99/2 = 4950개의 식이 나오는데, 이렇게 되면 N이 3일 때처럼 식을 아무렇게나 설정할 수 없다. 무슨 말이냐면, a+b, b+c, c+a... 의 값을 아무거나로 하면 안된다는 것이다.
음 백준님의 풀이를 들었는데, 처음 3개의 a+b, b+c, c+a값을 아무거나로 하되 단 짝수가 되도록만 하면 된다는 것 같은데, 정말인가? 음...백준님의 코드는 일단 모든 합이 순서대로 주어진다고 가정한 코드인 것 같다.
질문 게시판을 보니 dotorya님이 문제 입력이 순서대로 주어지는 건지 질문하시고 pichulia님은 순서대로 주어지는 것이 아니라고 답변하셨다. 그리고 두 분다 backtracking을 이용해서 푸신 것 같은데 음 어떻게 하지... pichulia님의 답변을 토대로 생각해봐야겠다.
주어진 합을 정렬하고 수열도 a1, a2, a3,..순으로 정렬되어 있다면, 가장 작은 합은 a1+a2일 것이다. 그리고 두 번째로 작은 합은 바로 a1+a3가 될 것이다. 이제 문제는 세 번재로 작은 합이다. pichulia님은 세 번째 숫자가 a1+a4인지, a2+a3인지 판단해야 하고, 이 이후는 backtracking으로 푸는 문제라고 답변하셨다.
a1+a4일 수도 있고, a2+a3일 수도 있다. 그럼 두 가지 경우를 다 해보는데, 만약 a1+a4가 세번째로 작은 수라면 이제 네 번째로 작은 수가 될 후보는 a2+a3와 a1+a5가 될 것이고 또 이 두 경우를 다 해보는데, a1+a5를 네 번째로 작은 수라고 하면 다섯 번재로 작은 수가 될 후보는 a2+a3와 a1+a6가 될 것이다. 이제 a2+a3를 다섯 번째로 작은 수라고 하면 a2+a4와 a1+a6가 후보가 될 것이고, 여섯 번째로 작은 수를 a2+a4라고 하면 이제는 a3+a4와 a2+a5와 a1+a6가 일곱 번째로 작은 수 후보가 될 것이다. 음... 이렇게 하다가 끝까지 가서 an-1, an의 합이 가장 큰 수가 되고, 만족하는 경우 탐색을 종료하고 답을 출력하면 될터인데... 쉬워보이지 않는다. 일단 구현이나 해볼까... 엄두가 안난다.
테스트 케이스가 순서대로 들어오는 입력만 있다면 통과할 수 있는 코드는 만들어 낼 수 있을 것이고, 일단 통과한 후 pichulia님이나 dotorya님의 backtracking code를 분석해보는 것도 한 방법이라고 생각한다. 음 그래 지금 9시 32분... 곧 집에 가야되고 시간도 애매한데 이걸로 오늘부터 내일 아침까지 즐겨야겠다.
일단 백준님 코드 참조해서 통과하는 코드부터 짜야지..
일단 통과는 했고, 지금 고수분들의 코드를 분석하는 중이다. 부디 늦어도 내일 아침까지는 끝내고 깨달음을 얻었으면 좋겠다. 이럴 때일수록 되새겨야 하는 말이 있다.
독서백편 의자현!
-------------------yukariko님의 코드를 보고 이해한 풀이----------------------------
일단 yukariko님의 코드를 먼저 봤는데, 겨우 이해가 됐다. 이해하고 나니 음 정말 감탄이 나왔다. 어떻게 이런 생각을 하실 수 있는거지... 코드도 간결하고 짧다.
yukariko님의 방식으로 설명해보자면,
일단 주어진 N*(N-1)/2개의 합을 정렬하고 보자. 원래 수열 a도 정렬되어 있다고 하면,
합 중 가장 작은 값은 a1+a2일 것이다. 그리고 두 번째로 작은 합은 a1+a3일 것이다.
세 번재로 작은 합은 a2+a3, a1+a4중 하나이므로 확실치 않다.
자 일단 확실한 정보는 a1+a2, a1+a3,...라는 것. 여기에 a2+a3만 알면
a1+a2+a1+a3+a2+a3 == 2(a1+a2+a3) 즉, a1+a2+a3를 알 수 있다. a1+a2+a3의 값을 알면 자연히 a1, a2, a3 값도 구할 수 있을 것이다.
그런데 a2+a3를 어떻게 알 수 있을까? 알 수 없으므로 다 해본다. a1+a2, a1+a3를 제외한 즉 정렬한 합들 중 세 번째 합부터 차례로 a2+a3라고 가정해본다. (다 해보되, 2*(a1+a2+a3)형태이므로 그 값이 짝수가 되는 경우만 허용된다.)
그럼 세 번째 합을 이용해서 a1+a2+a3를 구할 수 있고, 그에 따른 a1, a2, a3도 구할 수 있다.
자 여기서 map을 이용해서 기록을 하나 해야하는데, 바로 현재까지 구한 a의 값들(구하고자 하는 원래 수들)을 가지고 만들 수 있는 합을 만들어서 각 합이 몇개 존재하는지 기록한다. 그리고 처음에 map을 이용해 주어진 합들의 개수를 기록해놓은 것과 비교해서 현재 구하고 있는 a의 값들이 맞는지 체크해야 한다.
그런데 이제 a4부터는 어떻게 구할까? a4 == (a1+a4)-a1이다. aN==(a1+aN)-a1이다. a1을 기준으로 잡으면 나머지 모든 수를 구할 수 있다. 하지만 a1+aN을 알아내는 것이 문제다.
바로 아까 현재까지 구한 a의 값들을 기록해놓은 map때문에 쉽게 알아낼 수 있다. 현재까지 구한 a의 값들을 기록해놓으면, 예를 드는 것이 이해가 좋은데, a1, a2, a3를 구했다고 하자.
그럼 이 것들로 만들 수 있는 합들은 a1+a2, a1+a3, a2+a3이렇게 3가지이다. 그리고 지금 입력받은 합들은 오름차순으로 정렬되어 있어서, 처음부터 보면 작은 값부터 보게되는데, 지금까지 구한 합인 a1+a2, a1+a3, a2+a3를 제외한 가장 작은 값은 a1+a4가 될 수 밖에 없다.
그리고 이제 a4를 구해서 a1, a2, a3, a4로 만들 수 있는 합을 다 만들면 그것들을 제외한 가장 작은 합은 a1+a5가 될 것이고.. 이렇게 aN까지 다 구할 수 있게된다...
엄청나다. 이해했을 때 감탄했다. yukariko님은 어떻게 이런 생각을 하실 수 있는거지...알고보니 막 엄청 어려운 건 아니지만 그래도 난 이렇게 생각하지도 못했다. 음 아예 생각하기를 포기했던 것 같기도 하다... 반성해야겠다...
이제 방법을 알았으니 직접 짜봐야겠다. 사소하지만 주의할 점이 합의 개수는 n*(n-1)/2개라는 것이다.!! for문 뿐아니라 특히 정렬할 때도 n*(n-1)/2개라는 것을 기억해야 한다!!
맞게 짠 것 같았는데 계속 틀려서 이것 저것 다 해보다가 출력 형식이랑 변수를 다 int형으로 바꿨더니 맞았다. 근데 이것 때문에 시간 너무 많이 쓰기도 했고..왜 틀리는 지는 알아야 될 것 같아서 혹시 map<long long, int>부분이 지역변수로 선언되어있는데 너무 커져서 그런가 하고 전역변수로 뺐는데도 틀렸었다. 그래서 정답 코드(int형)에서 조금씩 long long으로 바꿔나가기 시작했고, 결국...
n이 2인 경우 0과 나머지 하나를 출력하는데 %lld로 출력한다. 근데 0에 LL을 안 붙인 것이 원인이었다... 헐... 주의해야겠다.
dotorya님이나 pichulia님이 하신 backtracking 방법은 일단 나중에... 좀 더 내공을 쌓은 후 도전해봐야 겠다. 나에겐 풀 문제가 많으니...
//참고 : 그리고 dotorya님 코드 보면서 생각하게 된건데, 이 문제는 딱히 들어오는 값의 범위 제한이 없다. 그래서 그런지 dotorya님은 long long으로 가정하시고 코드를 작성하신 것 같다. 문제에 입력 값의 제한이 없을 때는 dotorya님처럼 안전하게 하는 것이 좋은 방법같다.
백준님 설명 메모
처음 3개의 합을 결정하면 다 구할 수 있는데, 단 짝수가 되도록해야 한다!
백준님 풀이 하나 더...
A가 정렬되어있다고 가정하면 맨 앞의 합이 제일 작고, 맨 뒤의 두개의 합이 제일 크다...
댓글 없음:
댓글 쓰기