백준 10448 유레카[Java]

문제 자체 는 이해가 어렵지는 않다. t1 부터 2 씩 증가하는 삼각형을 생각 해 본다면 삼각형의 수는 손쉽게 구할수 있을것이다. 3 삼각형의 숫자를 더해서 표현가능한 자연수 판별 프로그램 이다. 범위를 보자.

 

3~1000 범위가 비교적 작다, 위에서 언급한 바와 같이 2부터 증가하는 for 문을 작성해 1000 이 어느정도의 범위 까지 겹치는지 확인해보자.

[1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 120, 136, 153, 171, 190, 210, 231, 253, 276, 300, 325, 351, 378, 406, 435, 465, 496, 528, 561, 595, 630, 666, 703, 741, 780, 820, 861, 903, 946, 990, 1035] 

 

총 45개 나왔다. 45 개의 범위 내에서 3 자리수 씩 순열을 돌리자 범위도 작은거 같으니 일단 해보자.

 

import java.io.*;
import java.util.*;

public class Main {
    static int[] arr;
    static boolean result;

    public static void main(String[] args) throws IOException {
        arr = new int[45];
        arr[0] = 1;
        for (int i = 1; i < arr.length; i++) {
            arr[i] = arr[i - 1] + i + 1;
        }

        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(bf.readLine());
        StringBuffer sb = new StringBuffer();

        for (int i = 0; i < N; i++) {
            int input = Integer.parseInt(bf.readLine());
            sb.append(sol(input) + "\n");
        }
        System.out.println(sb);
        bf.close();
    }

    static int sol(int input) {
        result = false;
        int index = indexCounter(input);
        int[] out = new int[3];
        permu(out, 0, input, index);
        return result ? 1 : 0;
    }

    static void permu(int[] out, int depth, int target, int index) {
        if (result)
            return;
        if (out.length == depth) {
            if (Arrays.stream(out).sum() == target) {
                result = true;
            }
            return;
        } else {
            for (int i = 0; i <= index; i++) {
                out[depth] = arr[i];
                permu(out, depth + 1, target, index);
            }
        }
    }

    static int indexCounter(int target) {
        int index = 0;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > target) {
                index = i - 1;
                break;
            }
        }
        return index;
    }
}

arr 를 static 으로 선언했다, 다른함수에서 사용하기 위해 저렇게 그냥 공용변수 처럼 내비뒀다.

result 는 순열을 돌아주는 재귀함수의 결과를 기록하기 위해 저렇게 위에다 선언했다.

 

먼저 주어진 수보다 큰수 까지 순열을 돌  이유가 없으니 인덱스를 정해줄때 고려해주자. 

순열 부분은 내코드가 이해가 안된다면 지난 포스팅을 보고 오자.(보러가기)

순열 에서 지난번과 다른점이 있다면 바로 방문처리여부 인데, 문제를 다시 읽어보면 중복해서 사용하는것을 허용해준다.(이것때문에 10분을 버그찾는다고 고생했다... ㅠㅠ) 그래서 따로 방문처리 없이 그냥 다음 재귀로 넘겨주면 된다... 

그렇게 해서 현재 out 에 들어간 아이들을 더해서 찾고자 하는 수와 동일한 값이라면 Result 를 업데이트 해준다.

result 가 현재 트루 라면 굳이 계속 재귀를 들어갈 이유가없으니 전부 종료해준다.

 

끝