반응형
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;
}
반응형
'Problem Solving > BOJ' 카테고리의 다른 글
백준 14791번 Tidy Numbers - C++(cpp) 풀이 (0) | 2022.03.23 |
---|---|
백준 14789번 Oversized Pancake Flipper - C++(cpp) 풀이 (0) | 2022.03.23 |
백준 12177번 Dreary Design - C++(cpp) 풀이 (0) | 2022.03.22 |
백준 12036번 Dance Around The Clock - C++(cpp) 풀이 (0) | 2022.03.21 |
백준 12969번 ABC - C++(cpp) 풀이 (0) | 2022.03.20 |
댓글