1965 상자넣기 : 가장 길게 커지는 수 랑 같은 풀이임

상자넣기 성공분류

시간 제한메모리 제한제출정답맞은 사람정답 비율

2 초

128 MB

11889

5604

4556

47.923%

문제

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

#include <iostream>
#include <algorithm>
using namespace std;

int arr[1002];
int boxx[1002];

int main(void)
{
	int n;
	cin >> n;

	for (int i = 0; i < n; i++)
		cin >> arr[i];
	boxx[0] = 1;
	for (int i = 1; i < n; i++)
	{
		boxx[i] = 1;
		for (int j = 0; j < i; j++)
		{
			if (arr[i] > arr[j])
			{
				boxx[i] = max(boxx[i], boxx[j] + 1);
			}
		}
	}
	cout << *max_element(boxx, boxx + n);
}

문제 가장 긴 증가하는 부분이랑 같은 풀이다. 

 

보충 설명하면 

만약 1 4 2 3 이렇게 되어 있는 수열이 있다고 하자. 

그럼 첫번째 for int i = 1 부분을 돌 때 4부터 시작 

j = 0이니까 1 4 를 비교하고 있다. 

arr[i] > arr[j] 즉 4는 1보다 크므로 

boxx[i] = max() 에 들어가게 됨 현재 Boxx[i] [j] 모두 동일하게 1 1 로 초기화되어 있다. 

따라서 boxx[i] 즉 boxx[1]은 1, 2중 2가 들어가게 된다. 

 

다음으로 i = 2 for 문을 돌게 되므로 1 4 2 를 비교하게 된다. 

1 4 까지는 동일하게 작용. 2부터 새로워진다. 

만약 i = 2 이면  boxx 는 현재 1 2 1 인 상태 

for j 문을 돌면 j = 0 1부터 비교 

1 2 비교시 2가 더 크므로 boxx[2] = max(1, 2) = 2 가 된다. 

j = 1 4를 비교하면 2 > 4 가 성립안하므로 if문 안에는 들어가지 않는다. 

 

다음으로 i = 3 for문을 돌때 1 4 2 3 을 비교 

1 4 2 까지는 동일하게 적용 3 부터 새로워진다. 

만약 i = 3 이면 boxx 는 현재 1 2 2 1 인 상태 

for j 문을 돌면 j = 0 1 2 비교 

j 가 0일 때 1 3 비교시 3이 더 크므로 boxx[3] = max(1, 2) = 2가 된다. boxx 는 현재 1 2 2 2 

j = 1일 때 2 3 비교시 3이 더 크므로 Boxx[3] = max(2, 3) = 3이 된다. boxx는 현재 1 2 2 3 

j = 2일 때 4 3 비교시 3이 더 작으므로 갱신 안함 boxx는 현재 1 2 2 3

 

따라서 max_element 에 따라 인덱스가 3 인 곳이 3으로 가장 크므로 

cout << 3 이 된다. 

참고로 max_element 는 헤더파일 #include algorithm이 필요하다. 

 

 

 

www.acmicpc.net/problem/11053

11053번: 가장 긴 증가하는 부분 수열