목록가장 긴 증가하는 부분 수열 (1)

JINWOOJUNG

[ DP - 11053 ] 가장 긴 증가하는 부분 수열(C++)

접근법 처음에는 0번째 부터 수열의 값을 체크 해 가면서 Max값을 다른 변수에 저장하고 해당 변수보다 큰 값이 있다면 Count를 1개씩 증가시키면서 변수를 Update하는 식으로 구현하였다. 너무 쉬운 감이 있었지만 역시 틀렸다. 10 20 5 12 17 30 다음과 같이 순열이 있다고 하자. 그러면 처음 접근법처럼 시도하면 Max = 10, Cnt =1일 것이다.하나씩 주어진 순열과 비교 해 나가면, Max = 20, Cnt = 1이고 그 뒤로 5,12,17은 전부 20보다 작아서 Count 하지 않고, 마지막 30만 Count 되어서 Max = 30, Cnt = 3으로 가장 긴 증가하는 부분 수열의 길이는 3이 된다. 하지만 5, 12, 17, 30 이 더 긴 증가하는 부분 수열로, 길이는 4가 ..
백준 2024. 6. 18. 14:01
이전 Prev 1 Next 다음