백준 11053번

동적 계획법 문제__백준 11053번

 

사진 출처 : www.acmicpc.net/problem/11053

 

처음 문제만 보고 이해하기 어려워 배열같은 표를 만들어 보면서 풀어봤다.

arr,dp배열 모두 0으로 초기화 하고 첫 번째 배열 1부터 시작하기로 했다.

10,20,10,30,20,50 순으로 입력을 했다면 처음 입력 받은 수로 dp는 +1이 되고 다음 배열과 비교하면서 처음 입력 받은 수 dp 값을 증감 혹은 유지 한다.

arr[0] = 0	arr[1] = 10	arr[2] = 20	arr[3] = 10	arr[4] = 30	arr[5] = 20	arr[6] = 50
dp[0] = 0	dp[1] = 1	dp[2] = 2	dp[3] = 1	dp[4] = 3	dp[5] = 2	dp[6] = 4

 

[풀이]

#include <iostream> using namespace std;   int arr[1001]; int dp[1001];   int main() {          int N;   cin >> N;       for (int i = 1; i <= N; i++) {           cin >> arr[i];     }          int result = 0;       for (int i = 1; i <= N; i++) {         int max = 0;         for (int j = 0; j < i; j++) {  //j는 i-1까지 비교             if (arr[j] < arr[i] && dp[j] > max) {                 max = dp[j];             }         }         dp[i] = max + 1;         if (dp[i] > result)                 result = dp[i];  //dp 갱신     }            cout << result << endl; return 0; }   Colored by Color Scripter