본 문제는 그냥 보자마자 번뜩 아이디어가 떠올랐다. 문제
내 생각은 현재를 기준으로 전의 값들을 비교하면 된다고 생각이 들었다. 즉, 다이나믹 프로그래밍 문제이다.
즉, 현재 값 > 전의 값 & 지금까지의 길이 < 전의 값까지의 길이
이다.
처음에는 이 문제가 가장 큰 증가하는 부분 수열인줄 알고 그렇게 풀었다가 거기서 변수만 조금 수정하면 되서 그렇게 성공했다. 다이나믹 프로그래밍같은 문제는 차근차근 생각하고 어떤 변수를 저장하고 사용할지를 생각하면 될 것이다.
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#define SIZE 1001
using namespace std;
int n;
int dp[2][SIZE] = { 0 };
void input() {
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &dp[0][i]);
}
void solve() {
dp[1][1] = 1;
for (int i = 2; i <= n; i++) {
int num = dp[0][i];
for (int j = 1; j < i; j++) {
if (dp[0][j] < num && dp[1][j] > dp[1][i] ) {
dp[1][i] = dp[1][j];
}
}
dp[1][i]++;
}
}
void print() {
int max = dp[1][1];
for (int i = 2; i <= n; i++)
if (dp[1][i] > max)
max = dp[1][i];
printf("%d", max);
}
int main(void) {
input();
solve();
print();
}
'공부 > 백준' 카테고리의 다른 글
[1049] 기타줄 (0) | 2019.11.05 |
---|---|
(11051번) 이항 계수 2 (0) | 2019.07.22 |