[C/C++] 백준 17946번 - 피자는 나눌 수록 커지잖아요

 

문제

새학기를 맞아 다이어트 중인 예찬이는 힘든 시간을 보내고 있다. 다이어트 중 너무 배가 고팠던 예찬이는 피자를 시켜 먹기로 한다. 피자 맛을 오래 느끼고 싶었던 예찬이는 피자를 k번 (1 ≤ k ≤ K) 의 칼질로 조각 낸 뒤, 조각을 하나하나 음미하려고 계획했다. 하지만 기다리던 피자가 도착하고 나서야 예찬이는 본인에게 칼이 없다는 사실을 알게 되었다. 때마침 칼이 있던 예찬이의 동기 윤희는 예찬이에게 다음과 같은 제안을 한다. 

“칼을 쓰게 해줄게! 하지만 피자를 다 자른 뒤에 칼질 한 번마다, 나한테 피자를 한 조각씩 증가 시키면서 줘. 다시 말해 칼질을 1번 하면 1조각을, 2번 하면 추가로 2조각을 얹어서 3조각을, 3번 하면 추가로 3조각을 얹어서 6조각을 달란말이야”

어차피 다이어트 중이었던 예찬이는 윤희의 제안이 나쁘지 않다고 생각해서 그 제안을 받아들이기로 한다. 하지만, 예찬이는 피자 맛을 오래도록 느끼고 싶기 때문에, 자신이 먹는 피자 조각의 수를 최대로 하고자 한다. 단, 피자 조각의 크기는 중요하지 않고, 칼질은 직선으로만 가능하다. 최대 칼질의 수 K가 주어질 때, 예찬이가 먹을 수 있는 최대 피자 조각 수를 구해주자!

입력

첫째 줄에는 테스트 케이스의 수 N이 정수로 주어진다. (1 ≤ N ≤ 1000)

다음 줄부터 N개의 줄에 테스트케이스가 한 줄에 하나씩 주어지고 각 테스트케이스에는 칼질의 최대 숫자 K이 정수로 주어진다. (1 ≤ K ≤ 109)

출력

각 테스트 케이스마다 예찬이가 먹을 수 있는 최대 피자 조각 수를 출력한다.

 

 

<코드>

#include<iostream>
#include<algorithm>
using namespace std;

int N, t;

int main()
{
	cin >> t;

	while (t--)
	{
		cin >> N;
		cout << 1 << '\n';
	}
	
}

 

 

풀이 방법

 

pizza : k번의 칼질로 만들어지는 피자의 최대 개수

give : 상납해야 할 피자 수

K	Pizza	Give
1	2	1
2	2+(2)	1+2
3	2+(2+3)	1+2+3
...	...	...
k	2+(2+3+4+...+k)	1+2+3+...+k

 

총 k번의 칼질로 예찬이가 먹을 수 있는 피자 수의 최댓값은 Pizza - Give이다. 따라서 수학적으로 식을 세워서 빼보면

Pizza = 2 + (k-1)(2+k)/2 = (k²+k + 2)/2

Give = (k²+k)/2

따라서 Pizza - Give = 항상 1이다.

 

 

www.acmicpc.net/problem/17946

17946번: 피자는 나눌 수록 커지잖아요