[BOJ] C++ 15486: 퇴사 2 - 테이블링이 어려운 DP

15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net 이전에 백트래킹으로 푼 문제와 똑같은데 입력의 크기가 많이 큰 문제이다. 이 정도 크기면 O(N^2)은 당연히 안되고 O(N)이나 O(N log N)으로 풀어야 한다. 풀이를 떠올리기 굉장히 힘들었는데, 그리디 하게 풀면 당연히 안되고 dp로 풀자니 테이블링이 쉽지 않았다. 테이블을 앞에서부터 탐색하면서 점화식을 찾으려 했는데 도저히 답이 나오지 않아서 정답을 살짝 참고했다. 바킹독님의 풀이에는 테이블링을 뒤에서부터 시작하면서 dp[..

2023.12.18