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

 

답은 쉽습니다. 1을 n번 출력하면 됩니다. 풀이는 어떻게 될까요

 

직선 n개로 평면을 분할할 때 분할되는 영역의 최대 개수를 \(a_n\)이라고 하면 \(a_n = \displaystyle \frac{n^2 + n + 2}{2} \)이 되는데요 (증명생략), 칼질 할때마다 1개, 2개, 3개.. 이렇게 피자 조각을 가져가니 n번 잘랐을 때 가져가는 조각의 개수는 \(\displaystyle \sum_{k=1}^{n} k = \frac{n(n+1)}{2} \)입니다.

따라서 항상 \(a_n - \sum k = 1\)이 됩니다.

결국 예찬이는 피자를 아무리 잘라봤자 1조각밖에 못먹는다는 슬픈 문제입니다. 그나마도 자를수록 조각이 계속 작아집니다.

 

그냥 감으로 때려맞춰도 되지만, 평면 분할 공식을 모르면 어려운 문제입니다.

#include <bits/stdc++.h>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);

	int n;
	cin >> n;
	while (n--) {
		cout << "1\n";
	}

	return 0;
}
반응형