링크
https://www.acmicpc.net/problem/1965
문제
정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 있다. 예를 들어 앞에서부터 순서대로 크기가 (1, 5, 2, 3, 7)인 5개의 상자가 있다면, 크기 1인 상자를 크기 5인 상자에 넣고, 다시 이 상자를 크기 7인 상자 안에 넣을 수 있다. 하지만 이렇게 상자를 넣을 수 있는 방법은 여러 가지가 있을 수 있다. 앞의 예에서 차례대로 크기가 1, 2, 3, 7인 상자를 선택하면 총 4개의 상자가 한 개의 상자에 들어가게 된다.
상자의 크기가 주어질 때, 한 번에 넣을 수 있는 최대의 상자 개수를 출력하는 프로그램을 작성하시오.
입력
파일의 첫 번째 줄은 상자의 개수 n (1 ≤ n ≤ 1000)을 나타낸다. 두 번째 줄에는 각 상자의 크기가 순서대로 주어진다. 상자의 크기는 1,000을 넘지 않는 자연수이다.
출력
첫째 줄에 한 줄에 넣을 수 있는 최대의 상자 개수를 출력한다.
예제 입력 1
8
1 6 2 5 7 3 5 6예제 출력 1
5예제 입력 2
10
1 2 3 4 5 6 7 8 9 10예제 출력 2
10아이디어 스케치
문제에서 제공된 예제 입력 1을 이용하여 테이블을 작성해보면
위와 같다.
이때 dp[i]는 i번째 상자에서 담을 수 있는 상자의 개수이다.
i번째 상자에서 넣을 수 있는 상자의 최대 개수를 구하기 위해서는 0 ~ i-1번째 상자를 탐색한다.
0 ~ i-1번째 상자들 중 i번째 상자의 크기보다 작은 상자를 선택한 후 (선택한 상자에 담을 수 있는 상자의 개수 + 1)이 (i번째 상자에 담을 수 있는 상자의 개수)보다 큰 경우 dp[i]의 값을 갱신한다.
이때 +1이 붙는 이유는 i번째 상자에 선택한 상자를 넣는 경우 최종적으로 상자의 개수가 +1이 되기 때문이다.
이후 현재까지 구한 넣을 수 있는 상자의 개수의 최댓값보다 현재 구한 값이 큰 경우 최댓값을 갱신한다.
위 과정을 모든 상자를 탐색할 때 까지 수행한 후 최댓값을 출력한다.
전체 코드
#include <stdio.h>
#include <stdlib.h>
int main()
{
int n;
int* arr;
int* dp;
int max = 0;
scanf("%d", &n); // 상자의 개수를 입력 받음
// 상자의 개수만큼 arr,dp 동적 할당
arr = (int*)calloc(n, sizeof(int));
dp = (int*)calloc(n, sizeof(int));
for (int i = 0; i < n; i++)
scanf("%d", &arr[i]); // 각 상자의 크기를 순서대로 입력받음
for (int i = 0; i < n; i++) {
dp[i] = 1; // 각 상자를 선택하는 경우는 기본적으로 1
for (int j = 0; j < i; j++) {
if (arr[i] > arr[j] && dp[i] < dp[j] + 1) // 현재 선택한 상자 이전의 상자들 중 현재 선택한 상자의 크기보다 작고, 들어있는 상자의 개수+1이 현재 선택한 상자에 들어있는 개수보다 큰 경우 갱신
dp[i] = dp[j] + 1; // 현재 선택한 상자에 위 조건을 만족하는 상자를 통째로 집어넣음
if (max < dp[i])
max = dp[i]; // 현재까지의 최대 개수보다 큰 경우 값을 갱신
}
}
printf("%d", max); // 결과 출력
// 동적할당 해제
free(arr);
free(dp);
return 0;
}제출 결과
