110541 [Swift][DP] 백준 11054번 (가장 긴 바이토닉 부분 수열) 요구능력 : DP에 대한 이해 코드설명 : 바이토닉 부분수열을 오해하고 문제를 풀었다. 증가하다가 가운데가 가장크고 점점 작아지는 수가 나오는줄알고 처음에는 증가하는 부분수열 + 인덱스저장 + 감소하는 부분수열로 풀었는데, 생각보다 간단하게 풀리는 문제였다. 이론적인 부분은 https://st-lab.tistory.com/136 엄청 잘 정리해 놓으셨다. 우선 가장 긴 증가하는 부분수열 dp를 구하고, 가장 긴 감소하는 부분수열 dp를 구해준다. 그리고 두 dp의 각 인덱스를 합쳐주고 1씩 빼주면 그게 두 수열을 합친것이다. 그래서 점점 작아지는 부분과 점점 커지는 부분이 합쳐져서 바이토닉 수열이된다. 내가 이해가 안갔던 부분을 위주로 설명하자면, 두 개를 합친다고 어떻게 하나의 바이토닉 수열이 되는가?.. 2021. 11. 15. 이전 1 다음