문제 40, 모든 쌍의 합, Pairsumonious Numbers, PC/UVa ID : 110508/10202, 인기도 : B, 성공률 : 높음, 레벨 : 4

문제 40, 모든 쌍의 합, Pairsumonious Numbers, PC/UVa ID : 110508/10202, 인기도 : B, 성공률 : 높음, 레벨 : 4

이 포스트를 만든 목적

• 생각 절차, 푼 방법, 고민거리 등을 기록하기 위해서 만들었다.
  

이 포스트의 준비물

• Mozila Firefox 5.0
  
• eclipse 3.6.1 + vrapper
  
• java
  

참조 문헌

• 스티븐 스키에나, 미구엘 레비야 저. Programming Challenges: 알고리즘 트레이닝 북. 서환수 역.
  Springer. 한빛미디어 초판 2쇄 2004.12.05. (문제 40, 모든 쌍의 합, Pairsumonious Numbers, p.161)
  

참조 링크

• http://plg1.cs.uwaterloo.ca/~acm00/010929/B.htm -- 문제 원문
  
• http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1143 -- 문제 원문

간략한 이야기/프로그램의 입출력

10 > n > 2 의 n이 주어졌을 때, n개의 정수들의 모든 쌍의 합의 갯수는 n(n-1)/2 이다. 이런 쌍의 합들이 n(n-1)/2 개 주어졌을 때, 합을 만들 수 있는 n개의 정수를 찾아라.

입력

• 각 입력 라인은 스페이스로 구분된 n과 n(n-1)/2 개의 정수 두개를 받는다.
  

출력

• 합을 만들 수 있는 n 개의 정수를 오림차 순으로 각 입력 라인당 한 라인에 출력하라.
  
• 만약 한개 보다 더 많이 답이 있을 경우, 답 중 아무거나 출력하라.
  
• 답이 없을 경우, "impossible"을 출력하라.
  

맛보기 코드

package Problem040PairsumoniousNumbers; import java.util.*; public class PairsumoniousNumbers { static public void main(String args[]) { Scanner sc = new Scanner(System.in); do { int n = sc.nextInt(); int pairSumonious[] = new int[n * (n-1) / 2]; for (int i = 0; i < pairSumonious.length; ++i) pairSumonious[i] = sc.nextInt(); PairsumoniousNumbersReal p = new PairsumoniousNumbersReal(n, pairSumonious); int[] numbers = p.findNumbers(); if (null == numbers) System.out.println("Impossible"); else { for (int i = 0; i < n; ++i) System.out.print(numbers[i] + " "); System.out.println(); } } while(true); } } class PairsumoniousNumbersReal { int n = 0; int expression[][] = null; int pairSumonious[] = null; int arrayNumbers[] = null; int abcd = 0; public PairsumoniousNumbersReal(int n, int ... pairSumonious) { this.n = n; this.pairSumonious = pairSumonious; this.arrayNumbers = new int[n]; // 가우스 소거법을 사용하기 위한 식을 만든다.(행렬쯤 된다) expression = new int[pairSumonious.length][n]; int expressionCount = 0; for (int i = 0; i < n; ++i) { for (int ii = i; ii < n - 1; ++ii) { expression[expressionCount][i] = 1; expression[expressionCount][ii + 1] = 1; ++expressionCount; } } } public int[] findNumbers() { // 모든 정수의 합을 구한다. 즉, a + b + c + d = abcd 로 표현한다. for (int i = 0; i < pairSumonious.length; ++i) abcd += pairSumonious[i]; if (0 != (abcd % (n-1))) return null; abcd /= (n - 1); // 올림차 정렬 Arrays.sort(pairSumonious); // n 이 3일 경우, 백트래킹 돌 필요가 없으므로, 그냥 계산한다. if (3 == n) { return findNumbersReal(); } else { // 백트래킹을 하되 최하값 두개와 최고값 두개는 이미 결정되었으므로 // 4개의 백트래킹을 하지 않는다. int back[] = new int[pairSumonious.length - 4]; Arrays.fill(back, -1); return backTracking(back, 0); } } public int[] findNumbersReal() { for (int i = 0; i < n; ++i) { // 값을 구하고 int processSum = -abcd; for (int ii = 0; ii < pairSumonious.length; ++ii) { if (1 == expression[ii][i]) processSum += pairSumonious[ii]; } arrayNumbers[i] = processSum / (n - 2); // 검산 한다. if (i > 0) { if (pairSumonious[i - 1] != arrayNumbers[0] + arrayNumbers[i]) return null; } } //DebugPrint.printArray("답 찾은 후", arrayNumbers); return arrayNumbers; } int[] backTracking(int[] back, int deep) { if (deep >= back.length) { // 백트래킹 결과를 보정한다 int temp[] = new int[back.length]; for (int i = 0; i < back.length; ++i) temp[i] = pairSumonious[back[i] + 2]; for (int i = 0; i < temp.length; ++i) pairSumonious[i + 2] = temp[i]; //DebugPrint.printArray("정렬 ", pairSumonious); return findNumbersReal(); } // 백 트래킹 for (int i = 0; i < back.length; ++i) { if (true == isContainValue(back, i)) continue; back[deep] = i; int[] numbers = backTracking(back, deep + 1); if (null != numbers) return numbers; back[deep] = -1; } return null; } // 배열에 특정 값이 있는지 확인 public static boolean isContainValue(int[] array, int value) { for (int i = 0; i < array.length; ++i) { if (value == array[i]) return true; } return false; } } class DebugPrint { static void printArray(String content, int[] arrayTarget) { System.out.println(content + Arrays.toString(arrayTarget)); } static void printArray(String content, int[][] arrayTarget) { for (int i = 0; i < arrayTarget.length; ++i) { printArray(content, arrayTarget[i]); } } static void print(String content, int answer) { System.out.println(content + answer); } }
package Problem040PairsumoniousNumbers; import static org.junit.Assert.assertTrue; import java.util.Arrays; import org.junit.Test; public class PairsumoniousNumbersTest { @Test public void testFindNumbers1() { PairsumoniousNumbersReal test = new PairsumoniousNumbersReal(3, 1269, 1160, 1663); assertTrue(Arrays.equals(new int[] { 383, 777, 886 }, test.findNumbers())); } @Test public void testFindNumbers2() { PairsumoniousNumbersReal test = new PairsumoniousNumbersReal(3, 1, 1, 1); assertTrue(Arrays.equals(null, test.findNumbers())); } @Test public void testFindNumbers3() { PairsumoniousNumbersReal test = new PairsumoniousNumbersReal(5, 226, 223, 225, 224, 227, 229, 228, 226, 225, 227); assertTrue(Arrays.equals(new int[] { 111, 112, 113, 114, 115 }, test.findNumbers())); } @Test public void testFindNumbers4() { PairsumoniousNumbersReal test = new PairsumoniousNumbersReal(5, 216, 210, 204, 212, 220, 214, 222, 208, 216, 210); assertTrue(Arrays.equals(new int[] { 101, 103, 107, 109, 113 }, test.findNumbers())); } @Test public void testFindNumbers5() { PairsumoniousNumbersReal test = new PairsumoniousNumbersReal(5, -1, 0, -1, -2, 1, 0, -1, 1, 0, -1); assertTrue(Arrays.equals(new int[] { -1, -1, 0, 0, 1 }, test.findNumbers())); } @Test public void testFindNumbers6() { PairsumoniousNumbersReal test = new PairsumoniousNumbersReal(5, 79950, 79936, 79942, 79962, 79954, 79972, 79960, 79968, 79924, 79932); assertTrue(Arrays.equals( new int[] { 39953, 39971, 39979, 39983, 39989 }, test.findNumbers())); } }

맛보기 사진

여담

• 좀 더 쉬운 방법이 있을거 같다는 생각이 든다.
  
• 가우스 소거법에서 아이디어를 얻어 풀었는데, 이게 보다 쉽게 푸는것을 방해한 것일 수 있다.
  
• 백트래킹을 좀 더 최적화 할 수 있을것 같으나, 능력이 부족하다.
  

:wq!