[BOJ 6128 // C++] Bessie's Secret Pasture

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 6128번 문제인 Bessie's Secret Pasture이다.
문제는 아래 링크를 확인하자.

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

6128번: Bessie's Secret Pasture

주어지는 10,000 이하의 자연수 N을 0 이상의 네 제곱수 a, b, c, d의 합으로 표현하는 경우의 수를 묻는 문제이다. (a, b, c, d의 순서가 다르면 다른 경우로 센다.)

 

a, b, c에 0부터 10,000까지의 제곱수들을 각각 직접 집어넣어 d가 제곱수가 될 수 있는지를 확인하는 브루트 포스 방식으로 문제를 해결할 수 있다.

 

미리 10,000 이하의 자연수에 대하여 각 수가 제곱수인지를 알아낼 수 있는 bool 배열을 만들어둔다면 구현을 편리하게 할 수 있다.

 

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int N;
bool issquare[10001];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;
	for (int i = 0; i < 101; i++) issquare[i * i] = 1;

	int cnt = 0;
	for (int i = 0; i < 101; i++) {
		int sumi = i * i;
		for (int j = 0; j < 101; j++) {
			int sumj = sumi + j * j;
			for (int k = 0; k < 101; k++) {
				int sumk = sumj + k * k;
				if (sumk > N) break;
				if (issquare[N - sumk]) cnt++;
			}
		}
	}

	cout << cnt;
}