Baekjoon

Baekjoon 1010번 다리 놓기

ppwag 2020. 11. 12. 12:46

문제

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

걸린 시간

00 : 26 : 29

풀이

C++

#include <bits/stdc++.h>
#define INF 1e9
#define all(c) c.begin(), c.end()
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int n, m;
int cache[30][30];

int dp(int w, int e){
    // 기저 사례
    if(w == n) return 1;
    // 메모이제이션
    int& ret = cache[w][e];
    if(ret != -1) return ret;
    // 재귀 호출
    ret = 0;
    for(int i = e; i < m; i++) ret += dp(w+1, i+1);
    return ret;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int tc;
    cin >> tc;
    while(tc--){
        cin >> n >> m;
        memset(cache, -1, sizeof(cache));
        cout << dp(0, 0) << "\n";
    }
    return 0;
}

실버 5 문제라고 머리로만 풀려다가 결국 펜을 잡아야 했던 문제.

다리가 겹치지 않게 놓이도록 하려면 다리가 놓인 다음 위치의 사이트부터 다리를 놓으면 된다. (조합)

중복은 놓은 다리의 개수가 같고, 마지막으로 놓은 다리의 동쪽 사이트가 같을 때 발생하므로 메모이제이션 해 주면 ac 를 받을 수 있다.

'Baekjoon' 카테고리의 다른 글

Baekjoon 1655번 가운데를 말해요  (0) 2020.11.13
Baekjoon 5213번 과외맨  (0) 2020.11.12
Baekjoon 16235번 나무 재테크  (0) 2020.11.12
Baekjoon 11657번 타임머신  (0) 2020.11.10
Baekjoon 16946번 벽 부수고 이동하기 4  (0) 2020.11.09

댓글