[AJ/DP] 버튼 누르기

문제

철수에게는 빨간색, 초록색, 파란색 세 개의 버튼이 있다. 버튼 하나를 누를 때 마다 특정 점수를 얻을 수 있으며, 철수는 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

---

풀이

	i=0	i=1	i=2
colorR[]	27	46 = Max(8+18, 28+18)	74 = Max(64+7, 67+7)
colorG[]	8	64 = Max(27+36, 28+36)	87 = Max(46+20, 67+20)
colorB[]	28	67 = Max(8+40, 27+40)	71 = Max(46+7, 64+7)

colorR, colorG, colorB 는 해당 색상을 선택했을 경우 갖는 최대값을 말한다.

 

i = 0 일 때 , 처음이니까 받은 값을 그대로 저장하고

i = 1 부터 R을 선택할 때 이전의 G, B 중  큰 값을 구하고 입력받은 R값을 더한다.

(이전 단계에서 R은 선택하지 못하고 G, B 만 선택이 가능하기 때문이다.)

 ....반복한다...

코드

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 colorR[] = new int[n];
        int colorG[] = new int[n];
        int colorB[] = new int[n];
        for (int i = 0; i < n; i++) {
            int r = sc.nextInt();
            int g = sc.nextInt();
            int b = sc.nextInt();
            if (i == 0) {
                colorR[i] = r;
                colorG[i] = g;
                colorB[i] = b;
            } else {
                colorR[i] = Math.max(colorG[i-1],colorB[i-1])+r;
                colorG[i] = Math.max(colorR[i-1],colorB[i-1])+g;
                colorB[i] = Math.max(colorR[i-1],colorG[i-1])+b;
            }
        }

        int max = Math.max(colorR[n-1], colorG[n-1]);
        max = Math.max(colorB[n-1], max);
        System.out.println(max);

    }
}