[백준] 11054번 - 가장 긴 바이토닉 부분 수열 (DP) - 결과 포함
www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 이전에 풀었던 11053번 가장 긴 증가하는 부분 수열 문제의 응용버전이다. 바이토닉 수열은 증가하는 부분과 감소하는 부분이 동시에 존재한다. 증가하는 수열과 감소하는 수열을 둘로 나누어서 메모하는 아이디어는 생각했지만 실제로 어떻게 구현할 지를 생각하지 못했다. 다른 분의 글을 참고해서 이해했다. 예를 들어 본다. 1 2 3 2 1 이라는 바이토닉 수열이 있다. 증가하는 부분은 1 2 3 감소하는 부분은 3 2 1 이다. 이전에..
개발 공부 (알고리즘)
2021. 4. 13. 01:45