백준 알고리즘, 9465 문제

---

풀이

한 스티커를 사용한 후 좌/우/상/하 에 위치한 스티커를 사용할 수 없다면

이동할 수 있는 위치는 대각선 뿐이다.

이러한 특징을 이용하여 문제를 풀어야한다.

규칙 1. 스티커 위치의 이동은 대각선으로 한다.

그 다음은 한번에 몇칸까지 이동할 수 있는가를 고려해봐야 한다.

이렇게 한번에 1칸, 2칸, 3칸 ... 등을 움직였을때

2 X N 의 최대 가중치가 어떻게 달라지는지 파악하는 것이 중요하다.

위 그림은 70 까지 가는 2가지 방법을 나타내었다.

파란색 : 50 에서 바로 70 으로 이동, 50 + 70 = 120

빨간색 : 30 과 10 을 거쳐서 70 으로 이동, 30 + 10 + 70 = 100

빨간색은 2 번 이동했음에도 불구하고 1 번 이동한 파란색 보다 값이 작다.

항상 이런 결과가 나오는 것은 당연히 아니다.

100 으로 이동하는 경우에는

30( [1][0] ) 에서 출발하면 1 번 이동으로 30 + 100 = 130 .

50( [0][0] ) 에서 출발하면 2 번 이동으로 50 + 50 + 100 = 200 .

그러므로 1 번 이동과 2 번 이동은 우리가 모든 경우를 확인해봐야 한다는 것을 알 수 있다.

자, 이제 3번 이동을 살펴볼 차례이다.

첫번째 칸 에서 3칸 이동 위치에 있는 10 으로 이동하고자 한다.

여기서 10 이라는 가중치는 중요하지 않다. 이 값이 아주 큰 값이더라도 변하는 것은 없다는 것을 미리 파악하자.

파란색 : 50 에서 바로 10 으로 이동, 50 + 10 = 60

빨간색 : 50 에서 50, 100 을 거쳐서 10 으로 이동, 50 + 50 + 100 + 10 = 210

주목할 점은 같은 위치에서 출발하여 3 칸의 이동으로 갈 수 있는 지점은 여러번 이동하여도 도달할 수 있다는 점이다.

따라서, 한번에 3 칸을 이동한 후의 가중치의 합은 1 칸, 2 칸 이동한 후의 가중치의 합보다 클 수 없다.

이러한 이유로 다음과 같은 규칙이 만들어진다.

규칙 2. 대각선 이동은 최대 2 칸으로 제한된다.

지금까지 많은 것을 알았지만

문제를 풀기위해선 한가지를 더 깨달아야 한다.

규칙 3. 첫번째 칸 ( [0][0] , [1][0] ) 중에서 하나는 무조건 선택된다.

왜그럴까?

이해하기 쉽도록 모든 가중치의 값이 같다고 가정해보자. (물론 값이 달라도 동일한 규칙이 적용된다.)

이럴 경우에는 무조건 가능한 많은 가중치를 선택해야 할 것이다.

규칙 3 과는 반대로 첫번째 칸을 절대로 선택하지 않는 경우를 생각해보자.

그런 경우는 없다.

2 칸 이동의 경우 가중치 선택이 더 적게 되기 때문에 위 경우에서는 최선의 선택이 아니다.

만약 파란색 원들이 선택되는 위치가 바뀐다면 [1][0] 이 아닌 [0][0] 이 반드시 선택되어야 할 것이다.

몇 번만 그려보면 위 규칙이 가중치가 모두 다른 경우에도 적용된다는 것을 알 수 있을 것이다.

이제 점화식을 만들어보자.

첫번째 칸 ( [0][0], [1][0] ) 은 반드시 선택된다고 했으니,

1. [0][0] 에서 출발하는 경우 와 2. [1][0] 에서 출발하는 경우  로 나누어 최종적으로 두 값을 비교해볼 것이다.

또한 가중치들이 저장되어 있는 배열(arr[][]) 외에 

이동에 따른 가중치가 누적될 또다른 배열(DP[][])을 하나 선언하여 사용할 것이다.

그러므로 DP[i][j] 배열에서 i 와 j 는 다음과 같은 의미를 가진다.

DP[i][j] = 100 --> ( i, 0 ) 에서 출발하여 ( i, j ) 까지 이동하며 얻는 가중치의 누적 합은 100 이다.

최종으로 점화식은 다음과 같다.

DP[0][j] = max( DP[1][j - 1] , DP[1][j - 2] ) + arr[0][j]

DP[1][j] = max( DP[0][j - 1] , DP[0][j - 2] ) + arr[1][j]

arr 배열에는 이동할 위치에 해당되는 가중치 값이 들어있다.

또한, 대각선 1 칸 이동과 2 칸 이동의 경우 중 큰 값을 더해준다.

---

코드

@github 에서 확인하기

/**
 * @site: https://www.acmicpc.net/problem/9465
 * @github: https://github.com/7772
 * @auth: Landon Park
 * @date: 2018. 07. 24
 */
#include <iostream>
using namespace std;
int max(int a, int b) {
    return (a > b) ? (a) : (b);
}
int main() {
    int test_case, arr[2][100001], DP[2][100001];
    int i, j, N;
    cin >> test_case;
    arr[0][0] = arr[0][1] = 0;
    DP[0][0] = DP[0][1] = 0;
    while ((test_case--)) {
        cin >> N;
        
        for (i = 0; i <= 1; i++) {
            for (j = 1; j <= N; j++) {
                cin >> arr[i][j];
            }
        }
        DP[0][1] = arr[0][1];
        DP[1][1] = arr[1][1];
        for (j = 2; j <= N; j++) {
            DP[0][j] = max( DP[1][j - 1], (DP[1][j - 2]) ) + arr[0][j];
            DP[1][j] = max( DP[0][j - 1], (DP[0][j - 2]) ) + arr[1][j];
        }
        cout << max(DP[0][N], DP[1][N]) << endl;
    }
    return 0;
}