문제
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
# 정리..
우선 점화식 도출이 너무 어렵다...
규칙을 찾는데 있어서는 뇌가 굳어버리는...
입력 값으로 1 3 5 2 7 3 이렇게 가정하고 풀어가면
arr = [1, 3, 5, 2, 7, 3]
우선 첫 번째 숫자인 1이 들어왔을 경우를 생각해보면
크게 1을 선택하는 경우와 선택하지 않았을 경우의 최댓값을 고려해볼 수 있다.
[1] 1을 선택하지 않았을 경우의 최댓값 : 0
[2] 1을 선택하였을 경우의 최댓값 : 1
여기서 정해진 최댓값을 해당 idx의 dp_table에 저장해두도록 하겠다.
dp_table = [ 1 ]
두 번째 3이 들어왔을 경우
이것도 마찬가지로 크게 3을 선택한 경우와 3을 선택하지 않았을 경우의 최댓값을 고려해볼 수 있다.
[1] 3을 선택하지 않았을 경우의 최댓값 : 1
[2] 3을 선택하였을 경우의 최댓값 : 4(1+3)
dp_table = [ 1, 4 ]
사실...여기까지는 주어진 입력 값이 1이상의 양수이기 때문에 무조건 더해준 값을 넣어주면된다.
세 번째 5부터는 고려해야할 경우가 더 생긴다.
문제의 조건 중 "연속하여 3개의 카드는 가져갈 수 없다" 라는 조건이 있다. 즉 1 3 5는 선택이 안된다는 것이다.
그러면 생각해볼 수 있는 경우의 수는 5와 3, 5와 1 이다.
즉 5를 가르키는 현재의 index(2)보다 1작은 요소의 합(3+5)과 혹은 2작은 요소의 최댓값(1)과의 합(1+5)를 비교해 볼 수있다.
[1] 5를 선택하지 않았을 경우의 최댓값 : 4
[2] 5를 선택하면서 이전 요소를 선택하는 경우의 최댓값 : 8(5+3)
[2-1] 5를 선택하면서 이전 요소를 선택하지 않는 경우에서의 최댓값 : 6(5+1)
여기서는 [2]번 경우인 8이 가장 크기 때문에
dp_table = [ 1, 4, 8 ]
네 번째 2... 여기까지 보면 점화식을 세울 수 있다. 잠시 현재 index는 3이다.
[1] 2를 선택하지 않았을 경우의 최댓값 : 8
[2] 2를 선택하면서 이전 요소를 선택하는 경우의 최댓값 :
(현재값 + 바로이전의 값 + 이전에서 한번 건너뛰고나서의 최댓값) 이전에서 한번 건너뛴다라는 뜻은
1 3 5 가 이미 들어왔고 2가 들어 왔을 경우를 우리는 지금 고려하고 있는 것이다.
2+5+1 여기서 1이 이전(5)에서 한번 건너뛴 값이다. 여기서는 1이지만 우리는 1이라고 생각 하면 안되고
건너뛴 index위치에서의 최댓값이라고 생각해야 한다.
그래서 (5+2+1) = 8 이 된다.
[2-1] 2를 선택하면서 이전 요소를 선택하지 않는 경우의 최댓값:
1 3 5 2 라고 봤을 때 우리는 2 + 이전요소를 한번 건너뛴 요소의 위치값이 아닌 위치의 최댓값으로 생각해야한다.
그래서 한번 건너뛴 요소의 위치값인 3이 아닌 위치의 최댓값인 4가 되는 것이다.
(2+4) = 6
이렇게 해서 index 3에서의 최댓값은 8인 된다.
dp_table = [ 1, 4, 8, 8 ]
여기서 점화식을 도출해보면
arr = [1, 3, 5, 2, 7, 3]
dp_table[4]를 구하기 위해서는
- 이전 요소의 최댓값 : dp_table[3]
- 현재 요소 포함, 이전요소 포함, 이전 요소에서 한칸 뛴 요소의 최댓값의 합 : arr[i] + arr[i-1] + dp_table[i-3]
- 현재 요소 포함, 현재 요소에서 한칸 뛴 요소의 최댓값의 합 : arr[i] + dp_table[i-2]
이렇게 3요소 에서의 max값을 찾아내면된다.
최종..
dp_table[i] = max(dp_table[i-1], max( (arr[i]+arr[i-1]+dp_table[i-3]), (arr[i]+dp_table[i-2]) )
#코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
import sys
if __name__ == "__main__":
input = sys.stdin.readline
n = int(input())
arr = list(map(int, input().split()))
dp_table = [0]*(len(arr))
dp_table[0] = arr[0]
dp_table[1] = arr[0]+arr[1]
dp_table[2] = max(dp_table[1], max(arr[2]+arr[1], arr[2]+arr[0]))
for i in range(3, n):
dp_table[i] = max(dp_table[i-1], max(arr[i]+dp_table[i-2], arr[i]+arr[i-1]+dp_table[i-3]))
print(dp_table[n-1])
|
cs |