알고리즘/동적 계획법 (DP)
백준 - 9465 스티커
문제 https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 서로 붙어있지 않은 스티커를 골라 가장 높은 점수를 구하는 문제였다. 문제 풀이 N이 100000이라 완전탐색으로 풀면 시간 초과가 날 것 같아서 dp로 풀었다. 처음에 예시만 보고 점화식을 만들어 풀었더니 틀렸다고 나와서 반례를 찾아 점화식을 수정했다. 0 : 50 1 : 100 50+50 vs 10 -> 100 2 : 200 100+100 vs 50+70 -> 200 3 : 2..
