본문 바로가기
BOJ

BOJ 10448 유레카 이론

by 홍code 2022. 3. 9.

문제링크 : https://www.acmicpc.net/problem/10448

 

10448번: 유레카 이론

프로그램은 표준입력을 사용한다. 테스트케이스의 개수는 입력의 첫 번째 줄에 주어진다. 각 테스트케이스는 한 줄에 자연수 K (3 ≤ K ≤ 1,000)가 하나씩 포함되어있는 T개의 라인으로 구성되어

www.acmicpc.net

요약

Tn = n(n+1)/2 로 이루어진 수열이 있다 이 수열의 숫자 세개를 이용해서 입력되는 숫자를 만들수 있다면 1, 만들지 못한다면 0을 출력하라.(숫자는 중복되도 됨)

풀이

만들어야 하는 숫자의 범위가 3<=K<=1,000이다. 수열의 숫자 세개로 K를 만들기 위해선 K보단 작아야 할것이다. (44x45)/2=990이고, (45x46)/2=1035이므로 1000까지 만드는데 확인해야할 수열크기가 44밖에 안된다. 미리 배열에 수열을 계산해서 넣어두고 3중포문으로 세개의 숫자의 경우를 전부 더해보고 비교해보면 된다.

코드

#include<iostream>
using namespace std;
int arr[45], n, k,chk=-1;
int main() {
	for (int i = 1; i <= 44; i++) {
		arr[i] = i * (i + 1) / 2;
	}
	cin >> n;
	while(n--){
		cin >> k;
		for (int i = 1; i <= 44; i++) {
			for (int j = 1; j <= 44; j++) {
				for (int p = 1; p <= 44; p++) {
					if (arr[i] + arr[j] + arr[p] == k) {
						cout << 1<<"\n";
						chk = 1;
						break;
					}
				}
				if (chk == 1)break;
			}
			if (chk == 1)break;
		}
		if (chk == -1)cout << "0" << "\n";
		else chk = -1;
	}
}

'BOJ' 카테고리의 다른 글

BOJ 1018 체스판 다시 칠하기  (0) 2022.03.09
BOJ 2503 숫자야구  (0) 2022.03.09
BOJ 3085 사탕게임  (0) 2022.03.09
BOJ 2231 분해합  (0) 2022.03.09
BOJ 2309 일곱난쟁이  (0) 2022.03.09

댓글