분류 전체보기
-
11053) 가장 긴 증가하는 부분 수열 c++백준코딩일기 2021. 2. 5. 15:31
문제 ) www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 풀이 ) 문제에서 dp 배열은 가장 긴 증가하는 부분 수열의 길이를 저장하는 배열로 사용했다. 1. 수열 A의 크기가 최소 1이라고 했으므로 dp[i] = 1 로 세팅하고 시작 2. A배열의 맨처음 수부터 계속해서 비교하기 위해서 j의 범위를 i까지 만으로 지정 3. 현재 비교할 수열의 값이 바로 직전의 값보다 클 경우 예를..