가장 긴 증가하는 부분 수열
문제가 점점 어려워진다. 으악.. 여러가지 시도해보았지만 오답이 많았다..
일단 풀이 방법만 적어 놓겠다.
D[N]에는 처음부터 N번째 까지의 값들 중 가장 긴 증가하는 부분 수열의 길이를 담기로 했다. 그 다음 D에 담겨있는 값중 최대값을 결과로 출력하면 된다.
기본값은 자기 자신만 있을 때의 길이인 1이다.
D[N]에는 처음부터 N - 1까지의 값들 중 자기보다 작은 값들을 찾고 그 길이 + 1을 담는데, 주의할 점은 가능한 경우는 여러가지가 존재할 수 있는데 그 중 최대값을 담아야 한다.
A[j] < A[i]
: 증가하는 수열이 될 수 있는지D[j] + 1 > D[i]
: D[i]
에 최대값이 담길 수 있게.
1 | N = input() |
뭔가 문제도 빡세지고.. 고민하는 시간도 길어지고 다른것도 이제 해야하다보니 4 ~ 5문제씩 풀기는 힘들지도 모르겠다 ㅠㅠ