가장 긴 감소하는 부분 수열

문제

언어

  • JavaScript

문제 풀이 step 1

  • 백준 11053번 - 가장 긴 증가하는 부분 수열 풀이
  • 감소의 반대는 증가, 증가의 반대는 감소이므로, 배열을 뒤집어서 가장 긴 증가하는 부분 수열의 길이를 구했습니다.
  • 풀이는 배열을 뒤집은 것을 빼고는 위의 풀이 링크와 다름이 없어서 별다른 풀이는 적지 않겠습니다.

느낀점

  • 꼭 다시 풀어볼 문제입니다.
  • 이런 문제를 볼 때 증가는 감소의 반대, 감소는 증가의 반대 라는 것을 떠올릴 수 있는 상태가 되는 것이 중요한 것 같습니다.
  • 배열을 뒤집는 방법도 있고, 배열의 모든 원소를 음수로 전환해서 푸는 방법도 있습니다.

소스 코드

const input = require("fs").readFileSync("/dev/stdin").toString().split("\n");

const solution = (input) => {
	const n = parseInt(input[0]);
	// reverse
	const numArr = input[1].split(" ").map(Number).reverse();

	// base
	const dp = [1];

	for (let i = 1; i < numArr.length; i++) {
		dp[i] = 1;
		for (let j = 0; j < i; j++) {
			if (numArr[j] < numArr[i] && dp[j] + 1 > dp[i]) dp[i] = dp[j] + 1;
		}
	}

	return Math.max(...dp);
};

console.log(solution(input));