문제설명
세개의 가방이 있다. 처음에는 각각의 가방에 1 이상의 값을 가진 자연수가 n1, n2, n3개 들어있다. ( 1 <= n1, n2, n3 )
풀이자는 한 가방에 담겨있는 수를 하나 꺼내 다른 가방에 들어있는 수 하나를 골라 합칠 수 있다. 꺼낸 자연수를 a, 다른 가방에서 합쳐지는 수를 b 라고 할 때, 꺼내진 자연수 a는 가방에서 사라지며 b 는 b-a 의 새로운 값을 가지게 된다.
모든 가방을 통틀어 하나의 수만 남을 때 까지 위 과정을 반복한다.
이 때 남을 수 있는 수 중 가장 큰 값을 구하시오.
예시
입력
2 4 1
1 2
6 3 4 5
5
출력
20
두번째 가방의 6, 5를 첫번째 가방의 1로 옮기면 [-10, 2] [3, 4] [5] 가 되고, 두번째 가방의 3, 4를 첫번째 가방의 1로 옮기면 [-10, -5], [] ,[5] 가 된다. -10과 -5를 세번째 가방의 5로 옮기면 [], [], [20]이 되며 20은 구할수 있는 가장 큰 수다.
나의 문제접근
어떻게 하면 마지막 남은 숫자가 커질까?
예시에서 보여준 것 처럼 마지막에 큰 수가 남기 위해서는 다른 가방에 있는 작은 수에 한번 옮긴뒤에 다른 한 가방의 한 숫자에 다시 한번 옮기는 방법이 직관적으로도 맞는 방법으로 보인다. 예시에서 첫번째 가방의 1의 경우에는 1 - (6 + 5) 였다가, 5와 합쳐질 때는 - 1 + ( 6 + 5 ) 가 되었다. 즉 두번 가방을 이동한 숫자는 다시 그 숫자를 더하게 되고, 한번 이동한 숫자는 자신의 크기만큼 숫자를 빼게 된다. 따라서 가장 작은 수에 한번 숫자를 몰아 준 뒤, 다른 가방의 한 숫자에 한번 더 옮기는 게 가장 큰 수를 만드는 비결인 것 같다. 그렇다면 가방별로 가장 작은 수 Am, Bm, Cm 을 찾고, 이중 가장 작은 두 수에 목표로 하는 가방의 수 하나만 남기고 나머지 수를 옮긴 뒤 다시 목표했던 가방으로 옮기면 가장 큰 수가 나올 것 같다.
예외는 없을까?
위의 추론대로라면 각 가방별로 가장 작은 수를 골라내고, 그중에서도 작은 두 수에 옮길 숫자를 모조리 합친다음에 하나의 숫자로 다시 옮기면 가장 큰 수가 완성될 것 같다.
이 생각을 위의 예시에 적용시켜보면 [1-(4+5+6)] ,[3-2],[5] 가 되고 5로 옮기면 [], [], [18]이 된다. 3이 2보다 크기 때문에 3을 2를 거쳐 5로 가게 하는 것이 더 큰수를 만들 수 있기 때문에 작은 수에 모조리 옮기고 한번 더옮기는게 항상 답은 아닌 것 같다.
이동비용을 계산하기 위한 문제풀이의 핵심
이동비용 : 마지막 하나남은 숫자에서 감소되는 값. 적은 비용으로 수를 옮길수록 마지막 숫자가 커지므로 최소비용을 계산하면 가장 큰 수를 계산할 수 있다.
1. 어떤 가방의 수를 2번에 걸쳐 이동하면 그 수는 마지막 숫자에 더해진다.
2. 어떤 가방(A)의 수를 2번에 걸쳐 목표가방(B)에 옮기기 위해서는 또 다른 하나의 가방(C)의 수를 거쳐야 한다.
2-1. 한 가방(A)의 수를 다른가방(B)으로 2번에 걸쳐 옮기기로 마음먹었다면, 또 다른 가방(C)의 하나의 숫자에 모두 합친뒤 다른가방(B)으로 옮김으로써 A->B로 숫자를 이동시키기 위한 비용(마지막 숫자에서 감소되는 값)을 최소화 할 수 있다.
2-2. 2-1을 거꾸로 생각하면 한 가방(A)의 수를 바로(한번에) 다른가방(B)에 옮기면 C 의 수를 비용으로 지불할 필요가 없어진다.
핵심 치고는 좀 긴 것 같다. 어쨌든 정리하면 다음과 같다. 각 가방의 가장 작은수를 Am, Bm, Cm, 가장 작은수를 제외한 나머지 수를 As, Bs, Cs 라고 할 때 모든 수를 가방 A수로 합치기 위한 최소의 비용은 (Bm+Cm) or (Bm+Bs) or (Cs+Cm) 이다. Bm 을 Cs가 A로 가기 위한 수로 사용하면 Bm 이 비용으로 지불되며, Cs를 무시하고 Bm을 Cm을 거쳐 A로 이동하면 Cs는 A로 바로 이동해야 하므로 비용이 Cs가 된다. (Bs, Cs)는 고려대상이 될 수 없다. 왜냐하면 Cs 또는 Bs의 개수가 0인경우 Bs or Cs는 Cm, Bm을 옮기기 위한 수단이 될 수 없기 때문이다. 또한 Cs와 Bs의 개수가 모두 1개 이상인 경우에도 그 비용은 항상 Bm, Cm보다 크거나 같다. Bm, Cm이 B와 C에서 가장 작은 수이기 때문이다.
위에서 정리한 대로라면 최소비용은 A, B, C 각각의 가방에 숫자를 모으는 경우의 최소비용후보 [(Am+As), (Bm+Bs), (Cm+Cs) , (Am+Bm), (Am+Cm), (Bm+Cm)] 중 하나이다.
느낀 점
문제가 복잡하지 않고 단순한 조건이었지만 정확한 답을 알기 위한 생각은 꽤나 많이 해야 했다. 쉬운 것 같으면서도 마냥 쉽지는 않았다. 풀이와는 별개로 문제의 자연수 범위가 커서 int형을 사용하면 오버플로우가 났는데, 그 점을 체크하지 못해 한번 오답이 났다. 알고리즘 문제를 풀때는 타입에 대해 한번쯤 더 생각하고 풀어야 겠다.
