백준 12181번 Googlander - C++(cpp) 풀이 + 그림 설명

---

 

1. i행에서 오른쪽으로 꺾으면 더 이상 i행 위는 방문할 수 없다.
2. 따라서 R-i행에서 오른쪽으로 꺾으면 i개 행, C-1개의 열이 있는 격자판에서 출발하는 상황과 같아진다.
3. 시작점에서 쭉 직진하다가 0~(R-1) 행에서 오른쪽으로 꺾는 모든 경우의 수를 더한다.

 

1. i행에서 오른쪽으로 꺾으면 더 이상 i행 위는 방문할 수 없다.

 오른쪽으로만 회전할 수 있기 때문에, 북쪽을 향하고 있는 상황에서 오른쪽으로 꺾으면 해당 지점보다 위에 있는 칸은 더 이상 방문할 수가 없다.

 

2. 따라서 R-i행에서 오른쪽으로 꺾으면 i개 행, C-1개의 열이 있는 격자판에서 출발하는 상황과 같아진다.

 따라서 시작점에서부터 쭉 직진하다가 R-i행에서 오른쪽으로 꺾으면 (i, C-1)인 격자판에서 출발하는 상황과 같아진다. 이제 다이내믹 프로그래밍을 이용해서 해결할 수 있다.

 

3. 시작점에서 쭉 직진하다가 0~(R-1) 행에서 오른쪽으로 꺾는 모든 경우의 수를 더한다.

 시작점에서 출발해서 처음으로 오른쪽으로 꺾는 경우는 총 r가지가 있으므로 이 경우를 모두 더해주면 된다. dp(r, c) = i 1부터 r까지 dp(i, c-1)의 합

반응형

---

#include <iostream>
#include <string.h>

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;

const int MAX = 26;
int R, C;
ll cache[MAX][MAX];

ll dp(int r, int c) {
    if (r == 1 || c == 1) return 1;
    
    ll& ret = cache[r][c];
    if (ret != -1) return ret;
    
    // i행에서 오른쪽으로 꺾으면 더이상 i행 위로는 방문할 수 없다.
    // r-i행에서 오른쪽으로 꺾으면 dp(i, c-1)인 상황과 같아진다.
    // 0행~(r-1)행에서 꺾는 모든 경우를 더한다.
    ret = 0;
    for (int i=1; i<=r; i++) ret += dp(i, c-1);
    
    return ret;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    memset(cache, -1, sizeof(cache));
    
    int T;
    cin >> T;
    
    for (int t=1; t<=T; t++) {
        cin >> R >> C;
        
        ll ans = dp(R, C);
        
        cout << "Case #" << t << ": " << ans << "\n";
    }

    return 0;
}