[Algorithm 풀이] 카드놀이

벌써 DP 까지 왔습니다! 나에게 박수를!!! 짝짝!!!!!!!!!!

이번 시간에는 dp를 위한 대표 문제를 풀어볼껀데요! dp는 부분 문제를 해결한 결과를 이용하여 전체 문제를 해결하는 방법입니다. dp는 크게 Top-down (분할 정복법) 방법과 Botton-up (중복 제거) 방법으로 나눌 수 있습니다.

dp 문제 풀이 순서는 다음과 같은 방법으로 풀면 쉽게 설계할 수 있습니다!!!

1) 부분 문제를 정의

2) 점화식을 구하라

3) 문제를 해결

그럼 문제를 한번 풀어보자!!!!!!!!!!!!!!!!

.

.

 

문제

N개의 카드가 주어지고, 각각은 자연수의 점수를 가진다. 철수는 이제 이 카드를 가져감으로써 카드에 적혀있는 수 만큼의 점수를 얻는다. 단, 카드를 가져갈 때 한가지 규칙이 있는데, 이는 연속하여 3개의 카드는 가져갈 수 없다는 것이다. 예를 들어, 6개의 카드 “1 3 5 2 7 3”가 주어질 경우, 3+5+7+3 = 18 만큼의 점수를 얻는 것이 최대이다. N개의 카드가 주어질 때, 얻을 수 있는 점수의 최댓값을 출력하는 프로그램을 작성하시오.

---

입력

첫 번째 줄에 N이 주어진다. ( 1 ≤ N ≤ 100,000 ) 두 번째 줄에 N개의 숫자가 주어지며, 이는 각 카드의 점수를 나타낸다.

출력

얻을 수 있는 점수의 최댓값을 출력한다.

---

예제입력

6
1 3 5 2 7 3

예제출력

18

---

 

코드

# Input
n = int(input())
data = list(map(int, input().split(" ")))

# Init
dp = [0] * n
dp[0] = data[0]
dp[1] = data[0]+data[1]
dp[2] = max(data[0]+data[2], data[1]+data[2], data[0]+data[1])

# Algorithm
for i in range(3, n):
  dp[i] = max(dp[i-1], data[i] + dp[i-2], data[i]+data[i-1]+dp[i-3])
print(dp[n-1])

 

⭐️ SOLUTION

 

1) DP Table을 이용해서 풀기.

2) DP[i] =>  0부터 i 까지의 카드가 있을 때 얻을 수 있는 최대값

3) DP[i] 기준,  1) i 번째 카드를 고르지 않은 경우. → DP[i-1]
                        2) i 번째 카드를 고르는 경우. 
                        2-1) i 번째 카드를 고르고, i-1번째 카드를 고르지 않은 경우. → data[i] + DP[i-2]
                        2-2) i 번째 카드를 고르고, i-1 번째 카드를 고르는 경우. → data[i] + data[i-1] + DP[i-3] 

4) 이 3가지 케이스 중 max 값 반환