BOJ G4 14002 가장 긴 증가하는 부분수열4 JAVA
14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 문제 읽기 일단 해당 문제는 흔히 LIS라고 하는 가장 긴 증가하는 부분 수열을 찾는 문제이다. 처음에 봤을 때는 tree모양이 생각났지만, 그려보니 아닌 것 같았다. 찾다 보니 DP라는 것을 알았다. 문제 풀기 N이 최대 1000이기 때문에 이중 for문을 통해 탐색해도 복잡도에 걸리지 않는 시간이다. 다음과 같은 과정을 통해 문제를 해결할 수 있다. 주어진 숫자 배열을 입력 받는..
2024. 3. 15.
