DP
-
9465 - 스티커Programming/BackJoon 2023. 3. 14. 13:25
1) 문제 설명 - 스티커를 선택하는데 최대 점수로 선택했을 때 점수를 출력! - - 위 그림에서는 점수가 50, 50, 100, 60인 스티커를 고르면, 점수는 260이 되고 이 것이 최대 점수이다. 2) 문제 아이디어 - DP로 풀수 있으며, 선택의 문제이다. - 점수를 규칙대로 채우면 마지막 값만 비교하면 된다. 처음에는 기본 값을 넣어준다 2번째 항에는 1번째 항의 결과값과 조건으로 주어진 점수표를 더해서 넣으면 된다. 단, 인접항 항은 더할 수 없으므로 대각선으로만 더해서 나간다. 예를 들면 dp[0][1]에 올수 있는건 dp[1][0] + 첫번째라인[1] 이다 문제에서 보면 3번째 열 이후에는 한번 선택을 하지 않는다. 그림으로 설명해보면, 4번째 열에서는 일부러 선택을 안한다. 왜냐하면 마지..