[BOJ][JAVA] 10448: 유레카 이론

https://www.acmicpc.net/problem/10448

10448번: 유레카 이론

 

import java.io.*;

class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int size = Integer.parseInt(br.readLine());
        int[] tri = new int[50];
        // 1~1000넘어까지의 삼각수 모두 저장
        for(int i=1; i<=50; i++){
            tri[i-1] = (i*(i+1))/2;
        }

        for(int i=0;i<size;i++){
            int target = Integer.parseInt(br.readLine());
            sb.append(check(target, tri)).append("\n");
        }

        System.out.println(sb);
    }
    static int check(int target, int[] tri){
        for(int i=0; i<50;i++){
            for(int j=i+1;j<50;j++){
                for(int k=j+1;k<50;k++){
                    if(tri[i]+tri[j]+tri[k] == target) return 1;
                }
            }
        }
        return 0;
    }
}

---

오답노트(푸는 동안 사고과정 및 개선점)

K가 작으니 삼각수를 미리 구해서 배열로 미리 만들어두고, 삼중포문을 돌려서 브루트포스로 해결하면 된다고 바로 떠올랐다.

문제를 제대로 읽지않아 중복해서 삼각수 세개를 더하는 것을 놓쳐 틀렸다...

---

정답코드

import java.io.*;

class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int size = Integer.parseInt(br.readLine());
        int[] tri = new int[50];
        // 대략 1~1000까지의 삼각수 모두 저장
        for(int i=1; i<=50; i++){
            tri[i-1] = (i*(i+1))/2;
        }

        for(int i=0;i<size;i++){
            int target = Integer.parseInt(br.readLine());
            sb.append(check(target, tri)).append("\n");
        }

        System.out.println(sb);
    }
    static int check(int target, int[] tri){
        for(int i=0; i<50;i++){
            for(int j=0;j<50;j++){
                for(int k=0;k<50;k++){
                    if(tri[i]+tri[j]+tri[k] == target) return 1;
                }
            }
        }
        return 0;
    }
}

삼중포문을 돌 때, 세 수가 중복가능하도록 바꿔서 해결했다.

 

"댓글, 공감 버튼 한 번씩 누르고 가주시면 큰 힘이 됩니다"