[실전 문제] 카드 놀이

1. 문제

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

 

 

 

2. 풀이

이 문제를 처음 접하게 되면, 특정 규칙을 찾기 위해 복잡하게 생각하는 경우가 많다. 필자 또한 처음에 이 문제를 접하고 가장 먼저 n개의 카드가 주어졌을 때 뽑을 수 있는 카드의 수 부터 생각했다. 하지만 그 경우에는 카드가 모두 주어졌을 때를 전제로 생각했다. 따라서 카드가 100000개 있을 때 주어지는 모든 입력값을 받고 처리하는 과정에서 복잡해진다는 것을 깨달았다.

 

이 문제의 경우에는 주어지는 모든 입력값을 받고 처리하는 방법이 아닌 입력이 되는 순서대로 처리를 하는 방법을 이용해야한다. 입력이 순서대로 주어질 때, 총 3가지로 나누어 생각해야한다.

• 입력된 카드를 뽑지 않을 경우
• 입력된 카드를 뽑을 경우
• 입력값과 그 전 값(2개)을 뽑을 경우

 

주어진 예제에서 처럼 입력이 들어온다고 가정하여 생각해보면 다음과 같다.

1

1이 들어왔을 때 뽑지 않을 경우 얻을 수 있는 최대값은 0

1이 들어왔을 때 뽑을 경우 얻을 수 있는 최대값은 1

1이 들어왔을 때 1과 그 전 값을 뽑을 경우 얻을 수 있는 최대값은 0

1

3

3이 들어왔을 때 뽑지 않을 경우 얻을 수 있는 최대값은 1 (3을 뽑지 않기 때문)

3이 들어왔을 때 뽑을 경우 얻을 수 있는 최대값은 4 (1 + 3)

3이 들어왔을 때 3과 그 전 값을 뽑을 경우 얻을 수 있는 최대값은 4 (1 + 3)

1

3

5

5가 들어왔을 때 뽑지 않을 경우 얻을 수 있는 최대값은 4 (5를 뽑지 않기 때문)

5가 들어왔을 때 뽑을 경우 얻을 수 있는 최대값은 6 (1 + 5)

5가 들어왔을 때 5와 그 전 값을 뽑을 경우 얻을 수 있는 최대값은 8 (3 + 5)

1

3

5

2

2가 들어왔을 때 뽑지 않을 경우 얻을 수 있는 최대값은 8 (2를 뽑지 않기 때문)

2가 들어왔을 때 뽑을 경우 얻을 수 있는 최대값은 6 (1 + 3 + 2)

2가 들어왔을 때 2와 그 전 값을 뽑을 경우 얻을 수 있는 최대값은 8 (1 + (5 + 2))

1

3

5

2

7

7이 들어왔을 때 뽑지 않을 경우 얻을 수 있는 최대값은 8 (7을 뽑지 않기 때문)

7이 들어왔을 때 뽑을 경우 얻을 수 있는 최대값은 15 (3 + 5 + 7)

7이 들어왔을 때 7과 그 전 값을 뽑을 경우 얻을 수 있는 최대값은 13 (1 + 3 + (2 + 7))

1

3

5

2

7

3

3이 들어왔을 때 뽑지 않을 경우 얻을 수 있는 최대값은 15 (3 + 5 + 7, 3을 뽑지 않기 때문)

3이 들어왔을 때 뽑을 경우 얻을 수 있는 최대값은 11 (1 + 5 + 2 + 3)

3이 들어왔을 때 3과 그 전 값을 뽑을 경우 얻을 수 있는 최대값은 18 (3 + 5 + (3 + 7))

 

이 과정을 모두 정리하면 다음과 같다.

• data[0]은 입력값을 뽑지 않을 경우 얻을 수 있는 최대값
• data[1]은 입력값을 뽑을 경우 얻을 수 있는 최대값
• data[2]는 입력값과 그 전 값을 뽑을 경우 얻을 수 있는 최대값

 

입력값	1	3	5	2	7	3
data[0]	0	1	4	8	8	15
data[1]	1	3	6	6	15	11
data[2]	0	4	8	8	13	18

그리고 마지막 카드가 주어진다면, 뽑지 않을 경우, 뽑을 경우, 그 전 값과 함께 뽑을 경우에서 구한 값들 중 최대값을 찾아주면 된다.

import java.io.*;
import java.util.StringTokenizer;

public class Main {

    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {

        int n = Integer.parseInt(br.readLine());

        int[] data = new int[3];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++) {
            int value = Integer.parseInt(st.nextToken());

            if(i == 0) {
                data[0] = 0;
                data[1] = value;
                data[2] = 0;
                continue;
            }
            int max = Math.max(data[0], Math.max(data[1], data[2]));
            data[2] = data[1] + value;
            data[1] = data[0] + value;
            data[0] = max;
        }

        bw.write(Math.max(data[0], Math.max(data[1], data[2])) + "");

        br.close();
        bw.flush();
        bw.close();
    }

}