«   2022/09   »
        1 2 3
4 5 6 7 8 9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28 29 30  
Archives
Today
57
Total
96,326
관리 메뉴

차근차근

[백준 1010] 다리 놓기 본문

대학교/Algorithm

[백준 1010] 다리 놓기

SWKo 2020. 2. 21. 18:24

0. 제목

  • 백준 1010 다리 놓기
  • BOJ 1010 다리 놓기
  • C++ 1010 다리 놓기

1. 문제

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


2. 풀이

  • mCn을 묻는 문제이다.
  • dp방식을 이용하여 값을 저장해놓는다.
  • dp[i][j]의 값은 왼쪽에 i개, 오른쪽에 j개가 있을 때 연결 방법의 개수이다.
  • 왼쪽에 3개, 오른쪽에 5개가 있다고 가정해보자.
  • 왼쪽의 가장 위에 것이 오른쪽 가장 위로 가면 나올 수 있는 방법 수는 dp[i-1][j-1] 이 된다.
  • 왼쪽의 가장 위에 것이 오른쪽 두번 째로 가면 나올 수 있는 방법 수는 dp[i-1][j-2] 이 된다.
  • 이렇게 쭉 반복하면 2차원 인덱스의 값은 j-1, j-2, ..., i-1 가 가능하다.
  • 점화식을 써보면 다음과 같다.
  • dp[i][j] = dp[i-1][j-1] + dp[i-1][j-2] + dp[i-1][j-3] + ... + dp[i-1][i-1]
  • 위 점화식을 반복문을 이용하고 매 테스트 케이스마다 dp를 초기화 시켜주면 된다.

3. 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
#include <cstring>
using namespace std;
 
int main(int argc, const char * argv[]) {
    int T, N, M;
    int dp[31][31];
    
    cin >> T;
    for(int i = 0; i < T; i++){
        cin >> N >> M;
        memset(dp, 0sizeof(dp));
        for(int i = 1; i <= M; i++){
            dp[1][i] = i;
        }
        
        for(int i = 2; i <= N; i++)
            for(int j = i; j <= M; j++)
                for(int k = j-1; k >= i-1; k--)
                    dp[i][j] += dp[i-1][k];
        
        cout << dp[N][M] << '\n';
    }
    
    return 0;
}
 

'대학교 > Algorithm' 카테고리의 다른 글

[백준 1922] 네트워크 연결  (0) 2020.02.23
[백준 4195] 친구 네트워크  (0) 2020.02.22
[백준 4948] 베르트랑 공준  (0) 2020.02.20
[백준 1197] 최소 스패닝 트리  (0) 2020.02.19
[백준 1476] 날짜 계산  (0) 2020.02.19
0 Comments
댓글쓰기 폼