백준. 11053번. 가장 긴 증가하는 부분 수열

병사 배치 문제를 풀다가 이게 기본형이라길래 이거 먼저 풀어봄

백준. 11053번. 가장 긴 증가하는 부분 수열

1. 문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

2. 입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

3. 출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

4. 풀이

7번에 최신 풀이가 있습니다.

• 각 단계에서 가장 긴 수열의 길이를 dp에 저장한다.
• 이전 항 중에서 현재 항보다 값이 작은 항의 값 중 최댓값 +1을 해서 현재 항에 저장한다.
• 모든 0 ≤ j < i에 대하여, D[i]=max(D[i], D[j]+1) if array[j] < array[i]
• 위의 점화식을 보고 코드를 짰다.

5. 처음 코드와 달라진 점

• 풀이를 보고 코드만 짠 거라 특별한 게 없다.
• 이번에도 scanf_s로 써서 한 번 고쳤다.
• 백준에 컴파일 에러가 점점 늘어간다.

6. 코드

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

using namespace std;

int arr[1000];
int dp[1000];

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

	for (int i = 0; i < n; i++) {
		scanf_s("%d", &arr[i]);
		dp[i] = 1;
	}

	for (int i = 1; i < n; i++){
		for (int j = 0; j < i; j++) {
			if (arr[j] < arr[i])
				dp[i] = max(dp[i], dp[j] + 1);
		}
	}

	int maxValue = 0;

	for (int i = 0; i < n; i++) {
		maxValue = max(maxValue, dp[i]);
	}

	cout << maxValue<<endl;
}

7. 풀이2

• DP로 풀었다.
• dy[i]은 i항을 마지막으로 하는 부분 수열 중 가장 긴 길이를 값으로 갖는다.
• 1번 항은 항상 1이다.
• 2번 항부터는 자기보다 작은 항을 찾는다.
  • 배열의 j번째 값이 i번째 값보다 작다면 j뒤에 i를 붙일 수 있다.
  • dy[j]에 j항을 마지막으로 하는 최대 부분 수열의 길이가 들어있기 때문에 해당 항 뒤에 i항을 이어 붙이면 최대 부분 수열의 길이는 dy[j] + 1이 된다.
  • dy[i]의 값과 dy[j] + 1 값을 비교하여 큰 값을 dy[i]에 저장한다.
    nums[j]는 항상 nums[i]보다 작아야 한다.
• 배열의 끝까지 dy의 갱신이 끝났다면 dy의 값들 중 최댓값을 찾아 리턴한다.

8. JS 코드

function solution(n, nums) {
  let answer = 0;
  let dy = Array(n).fill(1);

  for (let i = 1; i < n; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[j] < nums[i]) {
        dy[i] = Math.max(dy[i], dy[j] + 1);
      }
    }
  }

  answer = Math.max(...dy);
  return answer;
}