개요

[링크]백준 10448번: 유레카 이론

입력받은 자연수가 세 개의 삼각수의 합으로
나타낼 수 있는지 판단하여라.

접근 방식

일단 자연수 범위가 3~1000까지이므로
처음에 삼각수 배열을 미리 만들어놓고 갖다 쓰는게
효율적일거 같았다.

삼각수 세 개의 합을 구하는 과정을 고민하다가
어차피 40~45번째 삼각수에 1000이 존재하므로
O(n^3)의 복잡도로 구현해도 괜찮다고 생각했다.

#include<iostream>

using namespace std;
int arr[100] = { 0, };						//미리 배열에 선언

void solution(int& input);

void init(){								//미리 배열에 삼각수 값 넣어주기
	for (int i = 1; i < 100; i++) {
		arr[i] = (i * (i + 1)) / 2;
	}
}

void input() {								//입력 담당 함수
	int amount=0,in=0;
	cin >> amount;
	for (int i = 0; i < amount; i++) {
		cin >> in;
		solution(in);
	}
}

void solution(int& in) {
	int idx = 0;						//입력값보다 작은 삼각수의 인덱스
	for (int i = 1; i < 1000; i++) {	
		if (arr[i] > in) {				//처음으로 in보다 큰 값 나오면
			idx = i - 1;				//idx값 정해줌(필요이상으로 3중 for문에서 시간 안쓰기 위해)
			break;						
		}
	}

	for (int i = 1; i <= idx; i++) {	//3중 for문으로 3값 더했을때 값나오면 1 출력
		for (int j = 1; j <= idx; j++) {
			for (int k = 1; k <= idx; k++) {
				if (arr[i] + arr[j] + arr[k] == in) {
					cout << 1 << '\n';
					return;
				}
			}
		}
	}
	cout << 0 << '\n';					//못 찾으면 0 출력
	return;
}

int main() {
	init();
	input();
}

문풀후생

처음에 solution함수에서 idx값 정해줄 때,
break;를 안 적는 실수를 했다.
좀 더 꼼꼼해지자.