백준 1495 기타리스트

문제

풀이

2차원 dp로 풀수 있다. 처음에는 1차원 dp로 생각해서 풀려고 했으나 이미 진행된 값이 계산해야할 값을 덮어씌워서 불가능했다.

cache[n][p]: n까지 연주했을 때 n-1의 볼륨이 p일 때 n의 최댓값 

계산하지 않은 값과 불가능한 값을 둘 다 -1로 놓아서 시간초과가 발생했다. 주의하자…