[AJ/DP] 카드 놀이

문제

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

---

풀이

data 배열＼입력값	1	3	5	2	7	3
data[0]	0	1	4	8	8	15
data[1]	1	3 = 0+3	6 = 1+5	6 = 4+2	15 = 8+7	11 = 8+3
data[2]	0	4 = 1+3	8 = 3+5	8 = 6+2	13 = 6+7	18 = 15 +3

 

 

data[0] 은 입력값을 뽑지 않을 경우

data[1] 은 입력값만 뽑을 경우 

data[2] 는 입력값과 그 전 값 (총 2개)를 뽑을 경우 이다.

 

data[0]은 전 단계에서 max값을 취하고 (왜냐하면, data[0]은 입력값을 뽑지 않은 경우이기 때문에)

data[1]은 전 단계에서 data[0](안뽑은 경우)에 입력받은 값을 더하고

data[2]는 전 단계에서 data[1](하나 뽑은 경우)에 입력받은 값을 더한다.

 

.... 반복한다.

 

마지막에 data[0], data[1], data[2] 중 Max값을 찾으면 점수의 최댓값을 찾을 수 있다.

코드

import java.util.Scanner;
public class Main{


    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc = new Scanner(System.in);
        int n =sc.nextInt();
        int data[] = new int[3];
        for(int i=0;i<n;i++) {
            int value =sc.nextInt();
            if(i==0) {
                data[1] = value;
                data[0] = 0;
                data[2] = 0;
                }
            else {
                int max = Math.max(data[0],data[1]);
                max = Math.max(data[2], max);
                data[2] = data[1] +value;
                data[1] = data[0] + value;
                data[0] = max;
                
            }
        }
        int max = Math.max(data[0],data[1]);
        max = Math.max(data[2], max);
        System.out.println(max);
        

    }

}