백준 23317, 구슬 굴리기

개요

문제 링크
골드 5, DP
지점을 반드시 통과하며 좌우를 선택하여 이동하는 경로의 수

---

접근

1. 우선 주어진 지점들을 통과해야 하니까, (0,0) 출발점에서 m번째 지점까지 순차적으로 이동하면 됨. 마지막에는 이동가능한 (n,x)의 모든 점으로 이동하는 경로 곱해주면 됨.
2. (b,a)에서 (y,x)까지 이동하려면 어떻게 해야하나? 하면 조합 써주면 됨. (b,a)에서 (y,x)까지는 전체 이동이 |b-y|번, 그 중 왼쪽 이동이 |a-x|번 필요함. 즉 comb[dy][dx] 해주면 됨.
3. 이때 이동이 불가능 한 경우를 고려하면 (b,a), (y,x)에서 x가 a보다 작거나, x가 a+dy보다 크면 이동 불가. 이외에도 b==y이면 이동 불가 하기도 한데 x가 a보다 작은 경우를 제외하고는 comb[dy][dx]를 0으로 초기화하면 되긴 함.

---

Pseudo code

dist(a, b) {
    if (a.x < b.x)
        return 0
    if (b.x + dy < a.x)
        return 0
    return comb[dy][dx]
}
a[0] = {0,0}
for (i = 0~m)
    answer *= dist(a[i], a[i+1])
// 마지막엔 2^dy만큼 경우 있음
answer *= pow(2, (n-1)-a[m].y)

---

Source code

#include <bits/stdc++.h>
using namespace std;

const int N = 35;
const int M = 55;
using ld = long long;
typedef struct {
    ld x, y;
} space;
space a[M];
ld comb[N][N];
ld n, m;

int c1(space a, space b) {
    if (a.y != b.y)
        return a.y < b.y;
    else
        return a.x < b.x;
}

ld count(space a, space b) {
    ld dy = abs(a.y-b.y);
    if (b.x < a.x)
        return 0;
    if (a.x+dy < b.x)
        return 0;
    if (dy == 0)
        return 0;
    ld dx = abs(a.x-b.x);
    return comb[dy][dx];
}

ld get() {
    ld ans = 1;
    for (int i=0; i<m; i++) {
        ld v = count(a[i], a[i+1]);
        if (a[i].y == a[i+1].y && a[i].x == a[i+1].x)
            continue;
        if (!v)
            return 0;
        ans *= v;
    }
    ans *= pow(2, n-1-a[m].y);
    return ans;
}

int main() {
    for (int i=1; i<N; i++) {
        comb[i][0] = 1, comb[i][i] = 1;
        for (int j=1; j<i; j++)
            comb[i][j] = comb[i-1][j]+comb[i-1][j-1];
    }
    cin >> n >> m;
    for (int i=1; i<=m; i++)
        cin >> a[i].y >> a[i].x;
    sort(a, a+m+1, c1);
    cout << get();
}