[BOJ] 1965 - 상자넣기

Sierra·2022년 2월 7일
0
post-thumbnail

문제

정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 있다. 예를 들어 앞에서부터 순서대로 크기가 (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

Solution

#include <iostream>
#define MAX 1001
using namespace std;

int DP[MAX];
int Arr[MAX];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int N;
    cin >> N;
    int answer = 0;
    for(int i = 1; i <= N; i++) cin >> Arr[i];
    for(int i = 1; i <= N; i++){
        int maxValue = 0;
        for(int j = 1; j <= i; j++){
            if(Arr[i] > Arr[j]){
                if(maxValue < DP[j]) maxValue = DP[j];
            }
        }
        DP[i] = maxValue + 1;
        answer = max(answer, DP[i]);
    }
    cout << answer << '\n';
}

우선 모든 데이터를 입력받는다. 그 후는 좀 노가다긴 한데 각 인덱스별로 1번부터 i까지의 값을 탐색하면서 현재 인덱스 값 보다 작은 값이 있다면 그 값의 DP테이블 값이 현재까지 갱신된 최대값보다 크다면 최대값을 갱신해주는 것이다. 그 후 해당 인덱스의 DP테이블 값은 최댓값 + 1이 된다.

똑같은 문제로 가장 큰 부분 문자수열이라는 문제가 있다. 문제 지문만 다르지 완전히 똑같은 문제다.

DP로 무슨 점화식을 찾는 문제는 아니다. 약간 노가다 스러운 과정이 존재하지만 메모이제이션을 통해 더 큰 노가다를 방지하는 문제다. 가능하면 최대한 오름차순으로 쌓여가는 상자들이 값 변화폭이 적어야하니까 일일히 다 뒤를 뒤져보는 방식이다.

profile
블로그 이전합니다 : https://swj-techblog.vercel.app/

0개의 댓글