[백준/C] 20937번 떡국

문제

 

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

20937번: 떡국

---

Algorithm

"떡국 그릇 위에는 크기가 더 작은 떡국 그릇 하나를 쌓을 수 있다. 쌓은 떡국 그릇 위에 같은 방법으로 떡국 그릇을 또 쌓을 수 있다. 예를 들어, 크기가 4, 2, 3, 1인 떡국 그릇에 대해 4−3−2−1순서로 쌓을 수 있지만  3-4-2-1 순서로는 쌓을 수 없다. 이렇게 쌓은 한 개 이상의 떡국 그릇들을 떡국 그릇 탑이라고 하자."

이러한 조건을 가진 떡국 그릇 탑의 최소갯수를 구하는 문제이다. 

예시를 들어보자.

1.  5 4 3 2 1로 주어진 경우

이 경우는 5-4-3-2-1로 쌓을 수 있으므로 1개가 최소갯수이다.

2. 5 5 4 4 4 2 3 인 경우

이 경우는 5-4-3-2 , 5-4, 4로 쌓을 수 있으므로 3개가 최소 갯수이다.

문제에서 주어진 예시와 비교해보면 가장 많은 그릇의 크기의 개수가 ,즉 최소의 개수가 된다

딕셔너리를 이용하고 싶지만, C를 사용했으므로 배열을 선언해줘서 +1하는 식으로 구성하였다.

메모리를 줄이기 위해 가장 큰 그릇의 개수를 구해서 동적할당을 해주었다.

---

 

 

Code

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

int main() {
    int n;	//떡국 그릇의 개수
    int max_height=0;	//가장 큰 떡국 그릇의 크기
    int Count = 0;	//떡국 그릇 탑의 최소 개수
    scanf("%d", &n);

    int *bowl = (int *)malloc(n * sizeof(int));	//떡국 그릇을 담을 배열
    for (int i = 0; i < n; i++) {
        scanf("%d", &bowl[i]);
        max_height = (max_height > bowl[i])? max_height:bowl[i]; //최댓값 갱신
    }

    int *dict = (int *)calloc(max_height+1, sizeof(int));	//최댓값만큼 배열의 크기를 설정해주고 배열의 떡국 그릇의 크기에 +1을 해준다
    for (int i = 0; i < n; i++) {
        dict[bowl[i]]++;
    }

    for (int i = 0; i < max_height+1; i++) {	//그릇의 크기중 가장 원소의 개수가 많은 것이 탑의 최소갯수이므로 갱신해준다.
        if (dict[i] > Count) {
            Count = dict[i];
        }
    }

    printf("%d\n", Count);	//출력

    free(bowl);	//메모리해제
    free(dict); //메모리해제

    return 0;
}