문제 설명
삼각수는 다음과 같이 정의된다.
Tn = 1 + 2 + 3 + ... + n = n(n+1)/2예를 들면
T1 = 1
T2 = 3
T3 = 6
T4 = 10문제에서는 어떤 자연수 K가
정확히 3개의 삼각수의 합으로 표현될 수 있는지 판단해야 한다.
단,
- 같은 삼각수를 여러 번 사용해도 된다.
- 3개의 삼각수가 서로 다를 필요는 없다.
표현 가능하면 1, 아니면 0을 출력한다.
입력
첫째 줄에 테스트케이스 개수 T가 주어진다.
이후 각 줄마다 자연수 K가 하나씩 주어진다.
조건
3 ≤ K ≤ 1000출력
각 테스트케이스마다
K가 정확히 3개의 삼각수의 합으로 표현 가능하면 1,
불가능하면 0을 출력한다.
입력 예시
3
10
20
1000출력 예시
1
0
1문제 해결 아이디어
이 문제의 핵심은 다음과 같다.
K ≤ 1000즉, 수의 범위가 매우 작다.
그래서 가능한 삼각수를 미리 구해두고,
그 삼각수들 중 3개를 선택해서 만들 수 있는 모든 합을 확인하면 된다.
삼각수는
Tn = n(n+1)/2이므로 1000 이하의 삼각수는 많지 않다.
실제로 구해보면 대략 44개 정도밖에 되지 않는다.
즉,
- 1000 이하의 삼각수를 미리 구한다.
- 삼각수 3개를 고르는 모든 경우를 확인한다.
- 만들 수 있는 수를 미리 체크한다.
- 각 테스트케이스는 바로 답을 출력한다.
이 방식이 가능하다.
강의 풀이
강의에서는 먼저 전처리(preprocess)를 통해
1000 이하의 모든 유레카 수를 미리 계산했다.
코드
import java.util.Scanner;
class Main
{
static boolean[] isEurekaNumber = new boolean[1001];
public static void preprocess() {
int[] triangleNumbers = new int[50];
int triangleNumberCount = 0;
for (int i = 1; ; i++) {
int triangleNumber = i * (i + 1) / 2;
if (triangleNumber > 1000) break;
triangleNumbers[triangleNumberCount++] = triangleNumber;
}
for (int i = 0; i < triangleNumberCount; i++)
for (int j = i; j < triangleNumberCount; j++)
for (int k = j; k < triangleNumberCount; k++) {
int eurekaNumber = triangleNumbers[i] + triangleNumbers[j] + triangleNumbers[k];
if (eurekaNumber > 1000) break;
isEurekaNumber[eurekaNumber] = true;
}
}
public static void main (String[] args) {
preprocess();
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
while (T-- > 0) {
int K = sc.nextInt();
System.out.println(isEurekaNumber[K] ? "1" : "0");
}
}
}풀이 방식 해설
1. 삼각수 미리 구하기
먼저 1000 이하의 삼각수를 배열에 저장한다.
int triangleNumber = i * (i + 1) / 2;예를 들면
1, 3, 6, 10, 15, 21, ...이런 식으로 저장된다.
2. 삼각수 3개의 합 만들기
삼각수 3개를 선택하는 모든 경우를 확인한다.
for (int i = 0; i < triangleNumberCount; i++)
for (int j = i; j < triangleNumberCount; j++)
for (int k = j; k < triangleNumberCount; k++)이렇게 한 이유는
중복 사용은 가능
순서는 중요하지 않음이기 때문이다.
예를 들어
1 + 3 + 6
3 + 1 + 6
6 + 3 + 1은 모두 같은 경우이므로
순서를 고정해서 중복 계산을 줄였다.
3. 만들 수 있는 수 체크
삼각수 3개의 합이 1000 이하라면
isEurekaNumber[eurekaNumber] = true;로 표시한다.
즉, 나중에 어떤 수 K가 들어오면
isEurekaNumber[K]만 확인하면 바로 정답을 알 수 있다.
핵심 개념
1. 전처리
테스트케이스마다 매번 다시 계산하지 않고,
한 번만 미리 계산해두는 방식을 전처리라고 한다.
이 문제는 범위가 작기 때문에 전처리가 매우 효과적이다.
2. 삼중 반복문이 가능한 이유
보통 삼중 반복문은 부담스럽지만
이 문제는 삼각수의 개수가 적다.
1000 이하의 삼각수 개수는 많지 않기 때문에
충분히 빠르게 계산할 수 있다.
즉, 중요한 것은 단순히 반복문 개수가 아니라
실제 반복 횟수를 보는 것이다.
3. boolean 배열 활용
boolean[] isEurekaNumber = new boolean[1001];이 배열을 사용하면
각 숫자가 유레카 수인지 아닌지를 빠르게 기록할 수 있다.
예를 들어
isEurekaNumber[10] = true라면 10은 정확히 3개의 삼각수 합으로 표현 가능한 수라는 뜻이다.
시간 복잡도
전처리
삼각수의 개수를 N이라고 하면
전처리는 대략
O(N³)이다.
하지만 N 자체가 매우 작기 때문에 충분히 빠르다.
질의 처리
각 테스트케이스마다
O(1)이다.
배열만 바로 조회하면 되기 때문이다.
정리
이 문제는 처음 보면
각 테스트케이스마다 삼각수 3개의 합을 직접 찾으려고 할 수 있다.
하지만 K ≤ 1000이라는 제한을 보면
미리 만들 수 있는 수를 전부 구해두는 전처리 방식이 훨씬 효율적이다.
핵심은 다음과 같다.
- 1000 이하의 삼각수를 미리 구한다.
- 삼각수 3개의 합을 전부 계산한다.
- 만들 수 있는 수를 boolean 배열에 표시한다.
- 입력된 값은 배열 조회만으로 답한다.
즉, 이 문제는
작은 범위를 이용한 전처리 문제로 볼 수 있다.
