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;
}