Q34. 병사 배치하기

띠리링구 2022. 4. 26. 02:30

18353번: 병사 배치하기

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 2,000) 둘째 줄에 각 병사의 전투력이 공백을 기준으로 구분되어 차례대로 주어진다. 각 병사의 전투력은 10,000,000보다 작거나 같은 자연수이다.

www.acmicpc.net

문제를 읽고 든 생각은.. 오? 어려운데?

10분 고민해봤는데 1도 모르겠다;; 식을 어떻게 세워야되지..?

일단 모든 병사가 포함/미포함 되는 경우를 고려해서 각 경우마다 유효한 시퀀스인지 검사하는 방법을 취하려면 O(2^N * N)의 시간복잡도를 갖게된다. 내 목숨이 붙어있는 동안은 문제가 해결되지 않을것이다. 어떻게든 이전 연산 결과를 재활용할 방법을 생각해봐야된다.

와 이건 진짜 모르겠는데..ㅠ

아 진짜 자괴감든다 이건 정답 봐야알겠다;; ㅠ하 진짜

정답 보니까 가장 긴 증가하는 부분 수열 Longest Increasing Subsequence 문제라는데..

예전에 리트코드에서 서브시퀀스 관련 문제를 본적이 있었는데 난이도가 easy여서 정말 자괴감이 들었던 적이 있다

이것도 그러네.. 서브시퀀스 문제는 왜이리 난해할까 나한테;;

dp[i]가 array[i]를 마지막 원소로 가지는 부분수열의 최대 길이 라고 할때

dp 테이블 값을 모두 1로 초기화하고

모든 0 <= j < i에 대하여 D[i] = max(D[i], D[j] + 1) if array[j] < array[i]라는데

이 식이 가슴에 와닿게 직관적으로 이해가 되지 않는다.

ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ

이거보고 공부해봐야겠다

일단 영상에서도 처음엔 bruteforce에 대한 얘기를 한다.

오케 거기까진 나도 생각해봤어.

dfs로 탐색을 하는데

정보를 어떤 인덱스부터 시작하는 수열로 잡네..

그리고 그 사이에서 중복을 찾아서 캐싱

세상은 넓고 천재들은 많다

진짜 너무 명쾌한 설명이었다..

나중에 내 지식으로 만들어봐야지