[BOJ][C++] 백준 11053번 가장 긴 증가하는 부분 수열

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

1. 문제 정보

백준 온라인 저지 [11053번 가장 긴 증가하는 부분 수열] 문제의 링크입니다.

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.
예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.
정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

입력

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

출력

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

예제 입력1

6 
10 20 10 30 20 50

예제 출력1

4

시간 / 메모리 제한

1초 / 256MB

---

2. 생각

1. 주어진 수열에서 가장 긴 증가하는 부분 수열의 길이를 출력하는 문제입니다. 모든 원소에 대해서 해당 원소를 포함한 가장 긴 증가하는 부분수열의 길이를 구해야합니다.

2. 주어진 수열의 원소 1개, 2개, 3개, …, n개까지 늘려가며 증가하는 부분 수열의 길이를 구합니다. 따라서 dp[i]를 i 보다 작거나 같은 원소에 대해 가장 긴 증가하는 부분 수열의 길이(원소의 개수)로 정의하겠습니다.

3. 먼저 a배열을 입력받습니다. 그리고 i를 1부터(첫번째 원소) n까지(마지막 원소) 증가시키며 i보다 작은 인덱스의 원소 중에 어떤 원소가 i인덱스의 원소보다 작은지 판단합니다. i보다 작은 원소를 반복할 변수 j를 1부터 i보다 작을 때까지 증가시킵니다.

4. a[i]가 a[j]보다 크다면 증가하는 수열입니다. dp[i]보다 dp[j]가 클 때 dp[i]의 값에 dp[j]에 1을 더한 값을 넣어줍니다.

5. a[i]가 a[j]와 같다면 증가하는 함수가 아닙니다. 따라서 dp[j]의 값을 dp[i]의 값입니다.

6. dp 배열에서 가장 큰 값이 가장 긴 증가하는 부분 수열입니다.

   a 배열

   1	2	3	4	5	6
   10	20	10	30	20	50

   dp 배열

   i=1	2	3	4	5	6	개수
   10						1개
   10	20					2개
   		10				1개
   10	20		30			3개
   10				20		2개
   10	20		30		50	4개

3. 소스코드 (C++)

---

터미널의 입출력 화면 예제1

터미널의 입출력 화면 다른 예제