[실전 문제] 버튼 누르기

1. 문제

철수에게는 빨간색, 초록색, 파란색 세 개의 버튼이 있다. 버튼 하나를 누를 때 마다 특정 점수를 얻을 수 있으며, 철수는 1초에 한 번씩 버튼을 누를 수 있다. 물론, 특정 시간에는 세 개의 버튼 중에서 한 개의 버튼만을 누를 수 있다. 각 시간마다 특정 버튼을 눌렀을 때 얻는 점수는 모두 다를 수 있다. 예를 들어, 시간 1에 빨간색, 초록색, 파란색 버튼에 대한 점수가 3, 5, 7 로 주어질 수 있다. 이 경우에는 파란색을 누르는 것이 점수를 가장 많이 얻을 수 있다. 물론, 시간 2에 각 버튼에 대한 점수는 또 다를 수 있다. 버튼을 누를 때에는 한 가지 규칙이 있는데, 연속하여 색깔이 같은 버튼을 두 번 누를 수 없다는 것이다. 예를 들어, 시간 1에 초록색 버튼을 눌렀다면, 시간 2에는 초록색 버튼을 누를 수 없다. 이와 같은 규칙으로 각 시간마다 버튼을 누른다고 할 때, 철수가 얻을 수 있는 점수의 최댓값을 출력하는 프로그램을 작성하시오.

---

입력

첫 번째 줄에 철수에게 주어진 시간 N이 주어진다. ( 1 ≤ N ≤ 100,000 ) 두 번째 줄부터 N개의 시간에 대하여 빨간색, 초록색, 파란색 버튼을 눌렀을 때 얻을 수 있는 점수가 주어진다.

출력

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

예제 입력

3
27 8 28
18 36 40
7 20 8

예제 출력

87

 

 

 

2. 풀이

처음 이 문제를 접하고 예제 입력과 예제 출력이 이상하다고 생각할 수 있다. 그 이유는 연속으로 같은 색깔의 버튼을 누르지 않고 각 초의 최대값을 더한 값이라면 '28 + 36 + 8 = 72'라고 생각할 수 있기 때문이다. 하지만 이 문제에서 요구하는 것은 가장 마지막에 최대값이다. 따라서 예제 입력대로라면 '27 + 40 + 20 = 87'이 된다.

 

이 문제의 풀이는 정말 간단하다.

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[][] arr = new int[n][3];
        StringTokenizer st;
        for(int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            arr[i][0] = Integer.parseInt(st.nextToken()); // R
            arr[i][1] = Integer.parseInt(st.nextToken()); // G
            arr[i][2] = Integer.parseInt(st.nextToken()); // B

            if(i != 0) {
                arr[i][0] = arr[i][0] + Math.max(arr[i-1][1], arr[i-1][2]);
                arr[i][1] = arr[i][1] + Math.max(arr[i-1][0], arr[i-1][2]);
                arr[i][2] = arr[i][2] + Math.max(arr[i-1][0], arr[i-1][1]);
            }
        }
        bw.write(Math.max(arr[n-1][0], Math.max(arr[n-1][1], arr[n-1][2])) + "");
        br.close();
        bw.flush();
        bw.close();
    }

}