문제접근
1.
첫번째 접근
•
dp에는 길이가 담길 예정
•
처음 시작은 본인을 포함한 길이인 1로 초기화가 됨
•
[0] 인덱스에서부터 노란색 박스 범위 안에서 비교
•
빨간색원을 기준으로 값이 더 작은 녀석들과 비교
•
30 과 비교하여 더 작은 값을 가지는 위치의 dp값에 +1 을 하면서 더 큰 값을 업데이트 해나간다
//pseudo code
cin >> arr
dp배열 초기화
for // dp배열 인덱스
for // arr범위
if // 비교하는 대상이 j가 가리키는 값보다 크다면
dp[i] = max(dp[j] + 1, dp[i])
C++
복사
놓쳤던 부분
•
while문 이용시 입력값을 직접 이용하는 바람에 버그 발생
while(n--)
.
.
.
//이런식으로 입력 받은 N값을 직접 사용해서 버그 초래
C++
복사
코드
2016 KB
0 ms
#include <iostream>
#include <vector>
#include <algorithm>
int n;
std::vector<int> a;
std::vector<int> dp;
void input_setting()
{
std::ios_base::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
}
void input()
{
int i;
i = -1;
std::cin >> n;
a.resize(n);
dp.resize(n, 1);
while (++i < n)
std::cin >> a[i];
}
void solution()
{
int i;
int j;
int ans;
ans = 1;
i = -1;
while (++i < n)
{
j = -1;
while (++j < i)
{
if (a[i] > a[j])
dp[i] = std::max(dp[i], dp[j] + 1);
}
ans = std::max(ans, dp[i]);
}
std::cout << ans;
}
int main(void)
{
input_setting();
input();
solution();
return (0);
}
C++
복사
