[C++] 백준/BOJ - 14945 : 불장난

문제 이해 단계

https://www.acmicpc.net/problem/14945

14945번: 불장난

불이 있는 가장 위에서부터 시작해서
1초마다 아래, 오른쪽 아래, 왼쪽 아래로 퍼진다.

그리고 기웅, 민수도 위에서부터 시작하는데
이동 가능한 방법은 아래로 움직이거나, 오른쪽 아래로 움직이는 2가지다.

기웅, 민수는 맨 위 칸을 제외하고는 이동 중에 겹쳐서는 안 된다.
입력으로 n이 주어지고 직각삼각형으로 위의 그림처럼 주어진다.

항상 가장 마지막 n칸에는 문이 있을 때,
기웅, 민수가 탈출할 수 있는 경우의 수를 구하는 문제

 

---

문제 접근 단계

일단 문제에서 답을 구할 때 10,007을 나누라고 했다. 
이 말을 보자마자 '아 값이 엄청 크게 나오는구나'라고 생각했다.

그래서 경우의 수를 일일이 구했다가는 딱 봐도 시간초과가 뜰 것 같아서,
이건 수학적으로 풀어내거나 규칙을 찾아야 하는 문제라고 생각했다.

입력으로 주어지는 n의 범위도 최대 100까지인데, 값이 엄청나게 크게 나온다고 생각하니까
그냥 이거는 수학적이고 나발이고 그냥 DP라고 대놓고 알려주는 것 같았다.

그래서 뭔가 규칙이나 원리를 찾아보려고 했다.

일단 가장 처음에 이동하는 건 예외가 걸려있으니까 제외하고(겹쳐있을 때 이동하는 거니까)
n번째에서 n+1번째로 넘어갈 때, 나올 수 있는 경우를 살펴보자.

 

둘 사이의 거리를 제외하고, 나올 수 있는 움직임은 이 4가지가 끝이다.

4번째 움직임을 제외하고서는 둘의 거리가 어떻든 겹칠 수가 없다.

하지만 네 번째는 둘의 거리에 따라 겹칠 수가 있기 때문에
움직임이 제한될 수도 있다.

그리고 그다음 체크한 것은 "해당 문제가 DP 문제가 될 수 있는가?"였다.

생각해 보면, 첫 번째 그림에서 N = 3 일 때에서
아래로 한 칸 더 내려간다는 것은 어떤 의미일까?

(아래-아래-아래, 대각-아래-아래),
(대각-아래-아래, 아래-아래-아래)
이렇게 2개가 나온다.

즉, 결국 N = 2 일 때 나왔던 경우에 수의 일부분을 받아서
이를 이어서 만든 것이다.

이는 이전 결과를 받아온 것을 뜻하므로 DP라고 할 수 있는 것이다.

그래서 해당 DP를 세울 때, 단순히 크기 N만을 세우는 것이
아닌 둘 사이의 거리도 나타내어 4번째 움직임을 제어하기로 했다.

예를 들어 N = 4일 때, 둘 사이의 거리가 2라고 한다면 DP [4][2]라고 나타내는 것이다.

그럼 이제 DP [4][2]를 구한다고 해보자.

일단 올라가면서 거리가 변하지 않는 것들이다.
위에 그림으로 치면 1번과 3번 그림이다.

여기서 1,2번은 같고, 3,4번은 같기 때문에 중복 계산된다.
이래서 DP로 메모라이징을 해두는 것이다.

이를 DP 수식으로 나타내면
DP [4][2] + DP [4][2] = 2*DP [4][2]

 

이는 위에서 2번 그림에 해당된다.

내려가면서 거리가 멀어지기 때문에, 올라가면서 다시 거리가 좁아진다.
즉 이는 DP [4][1]이 된다.

 

이는 4번째 경우에 해당된다.

거리가 1인 경우에는 부딪히는 패턴.
만약 N = 3 인 그림이었다면, 해당 패턴은 존재하지 않는다.

이는 DP [4][3]이 된다.

해당 수식을 모두 정리하면
DP [5][2] = 2*DP [4][2] + DP [4][1] + DP [4][3]

이를 일반화하면

DP [N][K]
= 2*DP [N-1][K] + DP [N-1][K]+DP [N-1][K-1]+DP [N-1]{K+1]가 된다. 

이제 점화식을 만들었으므로 이를 구현하면 된다.

 

---

문제 구현 단계

 

#include <iostream>

using namespace std;

int d[101][101] = {0,};
int main(){
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    int n;
    cin >> n;
    d[2][1] = 2; // N = 2 일때는 임의로 초기화

    // N = 3 일때부터 시작
    for(int i = 3; i <= n; i++){
        for(int j = 1; j < n; j++){
            // 점화식
            d[i][j] = 2*d[i-1][j] + d[i-1][j-1] + d[i-1][j+1];
            d[i][j] %= 10007;
        }
    }
    int sum = 0;
    // N 일 때 거리가 두 사람 사이의 거리가 1 ~ N-1 경우를 다 더해줘야함
    for(int i = 1; i < n; i++) {
        sum+= d[n][i];
        sum %= 10007;
    }
    cout << sum;
}

DP문제이기 때문에 코드 자체는 간단하다.
그리고 점화식을 쓰는 것이 다다.

설명할 것은 우리가 구한 것은, 거리가 i일 때의 점화식이었기 때문이다.

답을 구하기 위해서는
두 사람 사이의 거리가 1 ~ N-1일 때의 모든 경우의 수를 다 더해줘야 한다는 것이다.

 

---

시행착오

이 문제가 DP인 줄은 알았지만
두 사람 사이의 거리를 토대로 DP를 만들 줄은 몰랐다.

답을 보고도 이해하는데 오래 걸린 문제였다.
역시 DP가 괜히 제일 어렵다는 말이 있는 게 아니다.

이게 골드 4라고?