[백준] 10448번 유레카 이론

생각

Github - https://github.com/hellojdh/Code/blob/master/src/baekjoon/q10000/Q10448.java

삼각수란 아래와 같이 증가하는 수를 의미한다.

숫자 K가 주어질 때, 3개의 삼각수로 K를 만들 수 있나 판단하여라.(같은 삼각수를 사용해도된다.)
가능하다면 1을 불가능 하다면 0을 출력하라.

처음 생각

3개의 삼각수만 더해서 숫자 K가 만들어지는가 만 판단하면 되기 때문에 완전 탐색을 진행하였다.

다음 생각

위의 그림에서 규칙을 보면 1 3 6 10 으로 2 3 4 씩 증가하는 규칙이 있기 때문에 반복문을 이용해서 구현을 해주었다.

▶ 반복문 3개를 사용하려 하였지만 3중 for문 부터는 보기가 좀 그래서 재귀를 통해 답을 구해주었다.

▶ 재귀에 카운트 변수 cnt가 3이 되었을 경우 이전까지 더해주었던 num과 들어온 인풋 값인 n을 비교해 같다면 result 를 1로 바꿔주었다. result가 1이 될시에는 더이상 탐색이 필요 없으므로 계속 return 시켰다.

▶ cnt가 0일 경우 삼각수는 num 자체를 바꿔주었고 나머지 cnt는 num에 더하여 주었다.

▶ num을 바꿔준 다음 초기화를 위해 해당 삼각수 사용후 num에서 해당 삼각수를 빼주었다.

다다음 생각

재귀를 사용하면 가지치기가 중요하므로 삼각수를 더할 때 해당 삼각수가 구해야하는 숫자를 넘어서는 경우 해당 cnt의 탐색을 return 해주었다.

방안

1) for문 보단 느릴 수 있지만 재귀를 통해 탐색을 하면 코드가 보기 편해진다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44

package baekjoon.q10000;   import java.util.Scanner;   public class Q10448 {     static int n;     public static void main(String[] args) {         Scanner sc = new Scanner(System.in);         int tc = sc.nextInt();         for(int i=0;i<tc;i++) {             n = sc.nextInt();             // 1~1000 으로 삼각수로 수가 증가하면 별로 많지 않고 3개로 만들 수 있는가 이므로             // 완전 탐색을 진행한다.             result = 0;             solve(0);             System.out.println(result);         }     }          static int result,num;     private static void solve(int cnt) {         // 되는 결과가 나왔다면 탐색이 필요 없으므로 return         if(result==1) return;                  // 삼각수 3개를 모으면 결과 확인         if(cnt==3) {             if(num==n) result = 1;             return;         }                  // 앞에서 부터 삼각수 들을 더해주자.         for(int i=1,t=2;i<1000;i+=t++) {             // i가 n을 넘는다면 더하지 않아도 된다.             if(i>n) return;             // cnt가 0 일 경우를 제외한 값은 더해주기             if(cnt==0) num=i;             else num+=i;             solve(cnt+1);             // 더했던 값 다시 빼주기             if(cnt!=0) num-=i;         }     } }