10-4: 카드 놀이

카드 놀이

 

문제

---

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

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class dp_cardgame_2 {


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

    private static boolean debug = false;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];
        int[] sum = new int[N];


        StringTokenizer st = new StringTokenizer(br.readLine());

        for (int i=0; i<N; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        sum[0] = arr[0];
        sum[1] = arr[0] + arr[1];
        sum[2] = Math.max(sum[1], Math.max(arr[2] + arr[1], arr[2] + arr[0]));

        for (int i=3 ;i<N; i++){
            sum[i] = Math.max(sum[i-1], Math.max(sum[i-2] + arr[i], sum[i-3] + arr[i] + arr[i-1]));
        }


        System.out.println(sum[N-1]);

    }
}