[JAVA]BOJ 10448, 유레카 이론

Brute Force 방식으로 풀어야 한다. 사실 이게 브루트 포스 방식인지 몰랐는데.. 내가 학교에서 푼 코딩은 대부분 브루트 포스였구나 하고 깨달았다. 아무튼~

 

<문제 분석>

T : 변수 K를 입력받는 횟수

K : 3개의 삼각수인지 확인할 변수

Tn[ ] : Tn을 미리 구해서 저장해놓은 배열

 

생각한 방식은.. 1. Tn을 미리 구해놓는다. 2. 재귀를 이용해 K - Tn을 한다. 3. K - Tn을 할 때마다 횟수를 더해준다. 간단히 요약하면 이렇게 된다. 다른 쉬운 풀이방법도 많은데 재귀가 더 익숙해서 재귀로..

 

1. Tn을 미리 배열에 저장해둔다

Tn = n * (n + 1) / 2 이므로 그냥 계산해서 미리 배열에 저장하면 된다. 그럼 몇번째 Tn까지 저장하면 될까..? 문제에서 K는 1000이하라고 했으므로 ' Tn <= 1000 ' 을 만족하는 가장 큰 Tn까지 저장하면된다. 계산을 해보니 .. n = 44 일때 Tn은 990으로 가장 적합하다. 45*46/2 는 1035로 1000을 넘어버린다. 

T1 T2 ... T43 T44 까지 저장하자. Tn[1] = T1 이런식으로 쓰고싶어서 for문의 i=1 부터 시작했다.

int[] Tn = new int[45];

// Tn 배열 생성
for(i=1;i<45;i++){
    Tn[i] = (i * (i + 1)) / 2;
}

 

2. K - Tn (CheckThreeTn 함수)

K보다 작은 Tn들 중 제일 큰 값을 먼저 뺀다. 거스름돈 문제랑 비슷하게.. 마치 우리가 900원을 거슬러줄때 100원 9개를 주는 것이 아니라, 500원 1개, 100원 4개를 주듯이..

for 문을 이용해 Tn[i]가 K보다 커지는 순간을 찾는다. 그때 Tn[i - 1]이 K보다 작은 Tn들 중에 가장 큰 값이다. i - 1을 n에 저장해준다.

for(i=1;i<45;i++){
    if(Tn[i] > K)
        break;
}

// K보다 작으면서 제일 큰 Tn[i] 인덱스 저장
n = i - 1;

 

3. 재귀호출 (CheckThreeTn 함수)

K 에서 Tn을 빼줄거다. 근데 제일 처음에 뺄 수는 CheckThreeTn 함수에서 정해준다.

예를들어, 10은 T4와 T3+T2+T1로 표현할 수 있다. (T4 = 10, T3 = 6, T2 = 3, T1 = 1) 이때 T4로 표현되는 것만 확인하고 끝내버리면 T3+T2+T1로 표현할 수 있다는걸 확인못하니까 .. 첫번째로 뺄 Tn이 T1이 될때까지 확인한다. 단, 3개의 Tn의 합으로 이뤄지는 경우를 찾았을때만 제외하고! (ans == 1)

 

빼면서 확인하기 때문에 이런식으로 코드를 짰다. recursiveCase() 이건 recursiveCase 함수를 호출해서 그 안에서 돌아간다는 뜻.. 표시 없는건 CheckThreeTn 함수이다. K = 10 으로 예를 들면..

 

n = 4, i = 4

recursiveCase(K - T4 = 0 임을 확인함) -> recursiveCase(return 0;) -> ans = 0

i--

 

n = 4, i = 3

recursiveCase(K(첫 재귀때 K는 10) - T3(6) = 4) -> recursiveCase(K(재귀하면서 값이 바뀌어서 K는 4) - T2(3) = 1) -> recursiveCase(K(1) - T1 = 0) ->  recursiveCase(basecase의 조건에 맞으므로 return 1;) * 3번 -> ans = 1

ans 가 1이므로 더 진행하지 않고 끝냄(break;)

return ans;

 

이런식이다. 헷갈리는데.... recursiveCase 함수를 보면 이해가 될거다.

public static int recursiveCase(int K, int[] Tn, int n, int cnt){
        int i;

        // base case
        if(K == 0 && cnt == 3) // 3개의 Tn의 합일때
                return 1;
        if(K == 0 || cnt > 3) // Tn을 3번 빼지 않았는데 이미 K가 0이 된 경우, Tn을 뺀 횟수가 3을 넘어가는 경우 더 계산할 필요 X
                return 0;

        // recursive case
            for(i=n;i>0;i--){ 
                if(K - Tn[i] >= 0){
                    if(recursiveCase(K - Tn[i], Tn, n, cnt + 1) == 1) // 3개의 Tn의 합일때
                        return 1;
                }
        }
        return 0; // 3개의 Tn의 합이 아닐때
    }

    public static int checkThreeTn(int K, int[] Tn){
        int i, n, ans = 0;

        for(i=1;i<45;i++){
            if(Tn[i] > K)
                break;
        }

        // K보다 작으면서 제일 큰 Tn[i] 인덱스 저장
        n = i - 1;

        for(i=n;i>0;i--){
            ans = recursiveCase(K, Tn, n, 0); 

            if (ans == 1) // 3개의 Tn의 합일때
                break;
        }
        return ans;
    }

 

 

---

아래는 전체 코드이다. 

import java.io.*;

public class BOJ10448 {
    public static int recursiveCase(int K, int[] Tn, int n, int cnt){
        int i;

        // base case
        if(K == 0 && cnt == 3) // 3개의 Tn의 합일때
                return 1;
        if(K == 0 || cnt > 3) // Tn을 3번 빼지 않았는데 이미 K가 0이 된 경우, Tn을 뺀 횟수가 3을 넘어가는 경우 더 계산할 필요 X
                return 0;

        // recursive case
            for(i=n;i>0;i--){ 
                if(K - Tn[i] >= 0){
                    if(recursiveCase(K - Tn[i], Tn, n, cnt + 1) == 1) // 3개의 Tn의 합일때
                        return 1;
                }
        }
        return 0; // 3개의 Tn의 합이 아닐때
    }

    public static int checkThreeTn(int K, int[] Tn){
        int i, n, ans = 0;

        for(i=1;i<45;i++){
            if(Tn[i] > K)
                break;
        }

        // K보다 작으면서 제일 큰 Tn[i] 인덱스 저장
        n = i - 1;

        for(i=n;i>0;i--){
            ans = recursiveCase(K, Tn, n, 0); 
            if (ans == 1) // 3개의 삼각수 합으로 이뤄질때
                break;
        }
        return ans;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int T, K, i;
        int[] Tn = new int[45];

        // Tn 배열 생성
        for(i=1;i<45;i++){
            Tn[i] = (i * (i + 1)) / 2;
        }

        T = Integer.parseInt(br.readLine());

        for(i=0;i<T;i++){
            K = Integer.parseInt(br.readLine());
            bw.write(checkThreeTn(K, Tn) + "\n");
            bw.flush();
        }
    }
}

 

늘 C언어로 재귀를 짰는데 자바로 재귀코드를 짜니까 포인터가 없어서 너무 불편했다. 지금 보면서도 return을 너무 많이 하는 것 같고.. 뭔가 지저분해보이는데 어떻게 더 수정을 못하겠다 ㅠㅠ.. 처음엔 메인에서 포인터로 &cnt를 보내고 cnt를 리턴하고 받은 cnt로 조건에 맞는지 확인하려고 했는데... 자바로는 그게 안되더라.. 아니 내가 못한걸지도.. 전역변수를 쓰면 되긴하지만 쓰기싫었다.