C++/BOJ
#6 - 20937번 떡국
yunhyegyeong
2021. 8. 9. 14:17
728x90
문제
함께 성장하는 개발자 지원 프로그램인 NAVER D2에서는 매년 개발자 컨퍼런스 DEVIEW를 개최한다.
2021년 DEVIEW에도 다양한 주제를 선보이기 위한 발표 준비 작업이 한창이다. 그런데 아주 큰 문제가 생겼다. 책상 위에 다 먹고 남은 떡국 그릇이 너무 많이 쌓여 작업을 진행할 수가 없다. 우연히 옆을 지나가던 당신이 이를 도와주기로 했다!
떡국 그릇 위에는 크기가 더 작은 떡국 그릇 하나를 쌓을 수 있다. 쌓은 떡국 그릇 위에 같은 방법으로 떡국 그릇을 또 쌓을 수 있다. 예를 들어, 크기가 4, 2, 3, 1인 떡국 그릇에 대해 4−3−2−1 순서로 쌓을 수 있지만 3−4−2−1 순서로는 쌓을 수 없다. 이렇게 쌓은 한 개 이상의 떡국 그릇들을 떡국 그릇 탑이라고 하자.
당신은 떡국 그릇 탑의 개수를 최소로 만들어 책상 위의 공간을 확보하려고 한다.
다음은 4, 2, 3, 1, 2인 떡국 그릇으로 쌓을 수 있는 떡국 그릇 탑의 개수의 예시이고, 최소 개수는 2개이다.
- 5개 : [4,2,3,1,2]
- 4개 : [4−2,3,1,2] 또는 [4−3,2,1,2] 또는 [4,3−2,1,2] 또는 ⋯
- 3개 : [4−2,3−1,2] 또는 [4−1,3−2,2] 또는 [4−3,2−1,2] 또는 ⋯
- 2개 : [4−2,3−2−1] 또는 [4−2−1,3−2] 또는 [4−3−2,2−1] 또는 ⋯
- 1개의 떡국 그릇 탑으로 만들 수 없다.
떡국 그릇들의 크기가 주어졌을 때, 떡국 그릇 탑의 최소 개수를 구해주자. 당신에게 감사의 표시로 NAVER D2에서 후원하는 SUAPC 2021w의 한 문제를 정답 처리해줄 것이다.
입력
다음과 같이 입력이 주어진다.
N
c1 c2 ... cN
출력
떡국 그릇 탑의 최소 개수를 출력한다.
제한
- N은 떡국 그릇의 개수이다. (1≤N≤500,000)
- ci는 i번째 떡국 그릇의 크기이다. (1≤ci≤50,000)
- 입력으로 주어지는 모든 수는 정수다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n;
cin >> n;
int a;
vector<int> vec;
for (int i = 0;i < n;i++) {
cin >> a;
vec.push_back(a);
}
sort(vec.begin(), vec.end());
int count = 0;
int temp = 0;
for (int i = 0;i < n - 1;i++) {
if (vec.at(i) == vec.at(i + 1))
count++;
else {
if (temp < count)
temp = count;
count = 0;
}
}
if (temp < count)
temp = count;
cout << temp + 1;
return 0;
}
|