백준 1965 c++ "상자넣기" -PlusUltraCode-

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

 

[필자 사고]

가장 긴 증가하는 부분수열 관련 문제이다.

자세한 설명은 아래 코드해설 부분에서 하겠습니다.

 

이 문제를 풀면서 조심해야 될점은 dp를 처음 초기화 할 때 1로 초기화 해야 된다.

그 이유는 일단 자신의 갯수를 포함시켜야 하기 때문이다.

 

이 문제를 풀면서 받은 인상은 특정 인덱스를 고른 뒤 그 앞에 있는 애들을 조사하고

현재 고른 인덱스의 값보다 작다면 dp를 갱신하는 작업을 수행한다.로 느꼇다.

 

[코드 해설]

1. 입력 처리 (Input 함수)

• N을 입력받아 배열의 크기를 결정한다.
• arr 벡터를 크기 N+1로 설정하여 입력 값을 저장한다.
• dp 벡터를 크기 N+1로 설정하고, 모든 값을 1로 초기화한다.
  • dp[i]는 arr[i]를 마지막 원소로 가지는 최장 증가 부분 수열 (LIS, Longest Increasing Subsequence)의 길이를 의미한다.
• N개의 정수를 입력받아 arr 배열에 저장한다.

2. 최장 증가 부분 수열 (LIS) 계산 (Game_Start 함수)

• i번째 원소를 끝으로 하는 최장 증가 부분 수열을 찾는다.
• i 이전의 모든 k (0부터 i-1) 값을 검사하여 arr[k] < arr[i]인 경우,
  • dp[i]를 dp[k] + 1과 비교하여 최댓값을 저장한다.
  • 즉, arr[k]에 arr[i]를 추가하여 만들 수 있는 부분 수열을 고려하는 방식이다.
• 마지막으로 dp 배열의 최댓값을 출력한다.

3. 프로그램 실행 (main 함수)

• Input()을 호출하여 데이터를 입력받는다.
• Game_Start()를 호출하여 LIS 길이를 계산한 뒤 출력한다.

[소스 코드]

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

vector<int> dp;
vector<int> arr;
int N;

void Input() {
	cin >> N;
	arr.resize(N + 1);
	dp.resize(N + 1,1);

	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}

}

void Game_Start() {

	for (int i = 1; i < N; i++) {
		for (int k = i - 1; k >= 0; k--) {
			if (arr[i] > arr[k]) {
				dp[i] = max(dp[i], dp[k] + 1);
			}
		}
	}
	cout << *max_element(dp.begin(), dp.end());
}

int main(void) {
	Input();
	Game_Start();
}