[자바] 백준 10448 - 유레카 이론 (java)

목차

문제 : boj10448

 

 

필요 알고리즘

• 브루트 포스
  
  • 단순히 모든 경우를 살펴보는 것으로 풀 수 있는 문제이다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

 

풀이

  문제를 약간 바꿔서 생각해보자.

X개의 숫자가 주어진다. 그 중 3개를 합한 값이 N인 경우가 있다면 1, 없다면 0을 출력하는 문제이다.

이 때, 단순하게 3개의 수를 골라 합쳐보면서 정말 있는지 없는지 확인해본다고 하자. 이 경우 시간 복잡도는 O(X^3) 이고, X가 충분히 작다면 이 풀이는 문제없이 가능한 브루트포스 풀이이다.

 

  다시 원래의 문제로 돌아오자. 뭔가 복잡해보이는 Tn 이라는 수식이 있는데, 딱히 상관없다. 위에서 말한 X개의 숫자가 주어지는 것과 마찬가지다. Tn은 이 문제에서 음수가 될 수 없으므로, 단순히 최대 K이하까지의 Tn만 구해두면 위에서 X개의 숫자가 주어진 것과 동일한 상황이란거다.

 

  Tn에서 n=44일 때 990이라는 값이 나온다. 즉, n=1부터 n=44까지만 Tn을 구하면 되며, 위의 예시에서 X는 44인 셈이다. O(44^3)으로 풀 수 있는 브루트포스 문제이다.

 

  로직은 다음과 같다.

1. n=1부터 n=44까지 Tn을 미리 구해둔다.

int[] t = new int[LEN];
for (int i = 1; i < LEN; i++) t[i] = i*(i+1)/2;

 

2. K를 입력받아, 44개의 Tn들을 3중 for문으로 직접 합쳐보다가 K와 동일해지면 1을 출력하면 된다. 없었다면 0을 출력하면 된다.

private boolean possible(final int[] t, final int n) {
    for (int i = 1; i < LEN; i++)
        for (int j = i; j < LEN; j++)
            for (int k = j; k < LEN; k++)
                if (t[i]+t[j]+t[k] == n)
                    return true;
    return false;
}

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1<<16);
    private static final int LEN = 45;

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        int[] t = new int[LEN];
        for (int i = 1; i < LEN; i++) t[i] = i*(i+1)/2;

        int tc = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        while (tc-->0) {
            int n = Integer.parseInt(br.readLine());
            sb.append(possible(t, n) ? 1 : 0).append('\n');
        }
        System.out.print(sb);
    }

    private boolean possible(final int[] t, final int n) {
        for (int i = 1; i < LEN; i++)
            for (int j = i; j < LEN; j++)
                for (int k = j; k < LEN; k++)
                    if (t[i]+t[j]+t[k] == n)
                        return true;
        return false;
    }

}