문제

---

내려가기 게임을 할 것이다. 이 게임은 첫번째 줄에서 시작해 마지막 줄에서 끝나는 게임이다.
N개의 줄에 0 이상 9 이하의 숫자가 3개씩 적혀 있다.

첫번째 줄에 적혀 있는 3개의 숫자 중 하나를 골라서 게임을 시작한다.
다음 줄로 내려가야하는데, 다음 줄로 내려갈때의 제약 조건이 있다.
내려갈 수 있는 위치는 바로 아래의 숫자 혹은 아래의 숫자와 붙어있는 숫자로 내려갈 수 있다. 아래의 그림을 보면 이해할 수 있을 것이다.

각각의 배열 칸은 숫자로 이루어져있다.
게임을 끝마쳤을때, 지나간 숫자들의 합이 나올 수 있는 경우의 수 중 최대값과 최소값을 구하면 된다.

입력

---

N은 1이상 10만 이하의 수
N개의 줄에 숫자를 3개씩 입력

출력

---

얻을 수 있는 최대값과 최소값을 출력

제한

---

시간 제한 : 1초
메모리 제한 : 4MB (java : 256MB)

풀이

---

처음 무작정 떠오른 알고리즘은 bfs였다.
하지만 값을 갱신하는 부분에 있어서 한계를 느꼈고 하나의 라인에 대한 값을 입력할때 마다 해당 라인까지의 최대값과 최소값을 저장할 수 있는 다이나믹 프로그래밍 방법을 떠올리게 되었다.

1. 각각의 라인의 입력 값을 저장할 변수 a1,a2,a3선언
2. 최대값을 저장할 변수들(max)과 최소값을 저장할 변수들(min) 선언
3. 계산한 값들을 저장할 임시 변수 tmp 선언
4. i행 1열의 최대값 = Math.max(이전행의 1열, 이전행의 2열) + i행 1열 입력 값
5. i행 2열의 최대값 = Math.max(이전행의 1열, Math.max(이전행의 2열, 이전행의 3열) + i행 2열 입력 값
6. i행 3열의 최대값 = Math.max(이전행의 2열, 이전행의 3열) + i행 3열 입력값
7. 최소값도 최대값과 비슷한 패턴으로 계산하면 된다.
8. 마지막 행의 최대값은 1~3열의 값중 최대값을 찾고 최소값은 1~3열의 최소값을 찾으면 된다.

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int a1,a2,a3;
        int max1 = 0;
        int max2 = 0;
        int max3 = 0;
        int min1 = 0;
        int min2 = 0;
        int min3 = 0;
        int tmp1,tmp2,tmp3;

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            a1 = Integer.parseInt(st.nextToken());
            a2 = Integer.parseInt(st.nextToken());
            a3 = Integer.parseInt(st.nextToken());

            tmp1 = Math.max(max1, max2) + a1;
            tmp2 = Math.max(max1, Math.max(max2, max3)) + a2;
            tmp3 = Math.max(max2, max3) + a3;
            max1 = tmp1;
            max2 = tmp2;
            max3 = tmp3;

            tmp1 = Math.min(min1, min2) + a1;
            tmp2 = Math.min(min1, Math.min(min2, min3)) + a2;
            tmp3 = Math.min(min2, min3) + a3;
            min1 = tmp1;
            min2 = tmp2;
            min3 = tmp3;
        }

        System.out.println(Math.max(max1, Math.max(max2, max3)) + " " + Math.min(min1, Math.min(min2, min3)));	    

결과

---