2012.01.05 20:11

오늘 페이스북에서 해커컵이라는 행사를 한다는 소식이 올라왔습니다. 뭔가 하고 자세히 보니 알고리즘 문제를 풀어서 상금같은걸 주나보네요. 

그래서 한번 공부할겸, 작년 문제를 풀어보았습니다.
(링크 :  https://www.facebook.com/hackercup/problems.php?round=4 )

그중  첫번째 문제(제일 쉽다고 해야 겠죠.....?ㅠㅠ) 에 도전해보았습니다.

문제는 이렇습니다.

Double Squares 

A double-square number is an integer 
X which can be expressed as the sum of two perfect squares. For example, 10 is a double-square because 10 = 32+ 12. Your task in this problem is, given X, determine the number of ways in which it can be written as the sum of two squares. For example, 10 can only be written as 32 + 12 (we don't count 12 + 32 as being different). On the other hand, 25 can be written as 52 + 02 or as 42 + 32.

Input

You should first read an integer N, the number of test cases. The next N lines will contain N values of X.

Constraints

0 ≤ X ≤ 2147483647
1 ≤ N ≤ 100

Output

For each value of X, you should output the number of ways to write X as the sum of two squares.

Example input 
5
10
25
3
0
1

Example output 
1
2
0
1
1
 

문제의 핵심은, 한 자연수를 두개의 자연수의 각 제곱으로 표현할때 몇가지로 표현 가능하겠느냐,...가 되겠습니다.
예를들어, 10이 들어오면, 10은 오직 3*3 + 1*1로 나타낼 수 있습니다. 따라서 방법은 1가지.(여기서 자리 바꾸는건 안센답니다.)


처음에 이 문제를 보자마자 왜 피타고라스가 생각났는지...ㅋㅋ

쨋든, 10분간 씨름하니 답이 얼핏 나오더군요.

먼저 n=1 부터 20까지 해서 적어보았더니, 규칙성을 발견할 수 있었습니다.

1 = 1*1 + 0*0
2 = 1*1 + 1*1
3 = X
4 = 2*2 + 0*0
5 = 2*2 + 1*1
   .
   .
   .
13 = 3*3 + 2*2
14 = X
15 = X
16 = 4*4 + 0*0
17 = 4*4 + 1*1
18 = 3*3 + 3*3
   .
   .
   .


저기서 중요한 부분이 바로 13~18이 부분입니다. 먼저, 들어오는 숫자를 z, 뒤이어 제곱이 되는 수를 차례로 a, b 라고 하겠습니다.

전제조건으로, b는 반드시 a보다 같거나 작습니다. (당연한 거죠.ㅋ)

먼저 13에서 a=3, b=2 입니다. 그러다가 16에서 갑자기 a=4로 올라갑니다. 앞의 규칙에선 a==b 이어야 a가 1 증가해서 다음 규칙들도 계속 a==b가 되면 a 1증가 이렇게 되서 16일때도 규칙성으로만 봐선 3*3 + 3*3 이 되어야 하죠.(규칙성만 봤을때 예기입니다.)

하지만, 갑자기 4로 뛰어버리는군요. 게다가 18에 와서야 다시 예상한 값인 a=3, b=3이 됩니다.

그러니까,  a=3, b=3 이 됬을때 입력한 z 보다 큰 값이 되니, 이때는 a를 1 증가하고 b를 0으로 만들어 다시 작게(4*4 + 0*0= 16 < 3*3 + 3*3) 만들어 줘서 다시 루프를 돌게 해줍니다. 
그러면, 16일때 a=4, b=0 이 맞게 됩니다. 

그다음, 이 루프를 빠져나갈때는 언제일까요?

바로, a의 제곱이 입력된 값z 보다 클때가 되겠습니다. 이건 범위를 더 줄일 수 있을것 같습니다.
일단 제가 생각한 방법은 이거라서...


일단, 코딩해 보았습니다. (테스트만 하면 되니 대충 넣어봤습니다.ㅋ)

public class DoubleSquares {

	public static void main(String[] args) {
		int n = 0;
		int[] testcase = {10, 25, 3, 0, 1, 26};		
		System.out.println("number : " + testcase[n]+", ways : "+solve(testcase[n++]));
		System.out.println("number : " + testcase[n]+", ways : "+solve(testcase[n++]));
		System.out.println("number : " + testcase[n]+", ways : "+solve(testcase[n++]));
		System.out.println("number : " + testcase[n]+", ways : "+solve(testcase[n++]));
		System.out.println("number : " + testcase[n]+", ways : "+solve(testcase[n++]));
	}
	
	private static int solve(int z){
		int a=0, b=0, ways=0;
		while(z >= a*a){
			if(z == (a*a + b*b)){
				ways++;
System.out.println("a : "+a+", b :"+b); if(a>b){ b++; }else{ a++; b=0;} }else{ if(z > (a*a + b*b)){ if(a>b){ b++; }else{ a++; b=0;} }else{ if(z <= a*a){ return ways; }else{ if(a>b){ b++; }else{ a++; b=0;} } } } } return ways; } }


위 코드의 실행 결과는 

a : 3, b :1
number : 10, ways : 1
a : 4, b :3
a : 5, b :0
number : 25, ways : 2
number : 3, ways : 0
a : 0, b :0
number : 0, ways : 1
a : 1, b :0
number : 1, ways : 1
a : 5, b :1
number : 26, ways : 1

가 나오게 됩니다.  아웃풋 예제와 답이 같네요,,,휴...ㅋ

다음엔 Peg Game를 풀어보도록 하겠습니다....만,, 풀 수 있을지...;; 


 * 2012-01-05 22:40 추가

다음 문제를 볼려고 했는데,,,해당 문제에서 새로 인풋이 있더군요. 위에 게시된 예제가 아닌...

그래서 실제 예제파일을 받아 열어보니 엄청나게 큰 수가 있습니다..ㄷㄷㄷㄷ 조건에 보니 범위가 int의 맥스같네요...

일단 제가 만든 알고리즘(.....)에 넣어서 돌려보니....역시 엄청 큰 수에서 연산이 오래걸리는군요...;;(10분째 연산중..;;) 

특히

2147483647
2147483645
2147483646

이 숫자들...에서 아직도 계산중입니다...(샌디브릿지 E2400 3.1GHz, 3.0GB) 

따라서 저게 답이 되진 못하겠군요... 좀더 수학적으로 접근해야 겠습니다.. 너무 노가다성으로 만든듯...ㅠㅠ

역시 만만치 않은 문제였습니다..ㅋㅋ 내일 다시 생각하기로...;;ㅠㅠ




 
저작자 표시 비영리 변경 금지
신고
크리에이티브 커먼즈 라이선스
Creative Commons License
Trackback 0 Comment 1
  1. double squares 2012.01.06 00:32 신고 address edit & del reply

    X = aa + bb (a >= b, a와 b는 음이 아닌 정수)라 하면 a <= floor(root(X))이기 때문에 a = floor(root(X))부터 시작하여 0까지 가면서 b = root(X - aa)를 만족하면 ways를 올리고 a < b이면 바로 루프를 빠져나가면 될 것 같습니다. 가장 큰 입력인 2147483647에 대해서도 floor(root(2147483647)) = 46340이니 이런 식으로 하면 계산도 별로 안 걸립니다.

    class DoubleSquares {
    public static void main(String[] args){
    for(int i=0 ; i<args.length ; i++){
    solve(Integer.decode(args[i]));
    }
    }
    private static void solve(int X){
    int a = (int)Math.floor(Math.sqrt(X));
    double b = .0;
    int numWays = 0;
    for(;;a--){
    b = Math.sqrt(X - a * a);
    if(a < b) break;
    if(b == (int)b) numWays ++;
    }
    System.out.println("number of ways for " + X + ": " + numWays);
    }
    }



티스토리 툴바