문제링크
https://www.acmicpc.net/problem/1010
문제
재원이는 한 도시의 시장이 되었다. 이 도시에는 도시를 동쪽과 서쪽으로 나누는 큰 일직선 모양의 강이 흐르고 있다. 하지만 재원이는 다리가 없어서 시민들이 강을 건너는데 큰 불편을 겪고 있음을 알고 다리를 짓기로 결심하였다. 강 주변에서 다리를 짓기에 적합한 곳을 사이트라고 한다. 재원이는 강 주변을 면밀히 조사해 본 결과 강의 서쪽에는 N개의 사이트가 있고 동쪽에는 M개의 사이트가 있다는 것을 알았다. (N ≤ M)
재원이는 서쪽의 사이트와 동쪽의 사이트를 다리로 연결하려고 한다. (이때 한 사이트에는 최대 한 개의 다리만 연결될 수 있다.) 재원이는 다리를 최대한 많이 지으려고 하기 때문에 서쪽의 사이트 개수만큼 (N개) 다리를 지으려고 한다. 다리끼리는 서로 겹쳐질 수 없다고 할 때 다리를 지을 수 있는 경우의 수를 구하는 프로그램을 작성하라.
입력
입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다.
출력
각 테스트 케이스에 대해 주어진 조건하에 다리를 지을 수 있는 경우의 수를 출력한다.
조건
- 시간 제한 : 0.5s
- 메모리 제한 : 128MB
해설
M이 8일 때 N의 값에 따른 다리를 지을 수 있는 경우를 따져보자.
N = 1 : 8
N = 2 : 7 + 6 + 5 + 4 + 3 + 2 + 1
N = 3 : (6 + ... + 1) + (5 + ... + 1) + ... + 1
N = 4 : {(5+...+1)+(4+...+1)+...+1} + {(4+...+1)+...+1}+...+1
...여기에서 찾을 수 있는 규칙은 N이 증가할수록 N-1에서 구한 값들이 부분적으로 사용된다는 것이다. N=3일 때 첫번째 괄호의 값은 N이 2일 때의 1번째 원소를 제외한 나머지의 합과 같고, 두번째 괄호의 값은 2번째 원소까지 제외한 나머지의 합과 같다. 즉, N[k]의 값은 N-1[k+1 ~ M]의 합과 같다.
풀이
먼저 M 값 크기의 vector를 만들어 1~M의 값을 역순으로 넣어준다.
vector<long> dp(M);
for(int i = 0; i < M; i++) {
dp[i] = M-i;
}
반복문을 통해 N[k]의 값은 N-1[k+1 ~ M]임을 구현하여준다. i는 N의 값에 따라 dp의 단계가 올라감을, j는 현재 바꾸고자 하는 dp값을, k는 N-1에 해당하는 값들을 가져오는 역할을 한다. 반복문을 통해 i 단계에서 dp[j] 에는 i-1 단계의 dp[j+1 ~ M] 값의 합으로 초기화된다.
for(int i = 2; i < N; i++) {
for(int j = 0; j < M; j++) {
long temp = 0;
for(int k = j+1; k < M; k++) {
temp += dp[k];
}
dp[j] = temp;
}
}M이 8일 때 dp 벡터에 담겨있는 값
i = 2 : 8 / 7 / 6 / 5 / 4 / 3 / 2 / 1
i = 3 : (6 + ... + 1) / (5 + ... + 1) / ... / 1
i = 4 : {(5+...+1)+(4+...+1)+...+1} / {(4+...+1)+...+1} / ... /1
...
여기에서 만약 구하고자 하는 조건의 N값이 4라면, 계산하여야 하는 값은 {(4+...+1)+...+1} + {(3+2+1)+(2+1)+1} + {(2+1) + 1} + 1 이고, 이 값은 i=4 단계의 첫번째 원소를 제외한 나머지 원소의 합과 같다. 이를 식으로 나타내면 아래와 같이 나타낼 수 있다.
long sum = 0;
for(int i = 1; i < M; i++) {
sum += dp[i];
}
cout << sum << '\n';
이를 T번 반복하면 된다!
코멘트
이게 DP 푸는 맛인가..?
코드
#include <iostream>
#include <vector>
using namespace std;
int main() {
// ios::sync_with_stdio(false);
// cin.tie(0); cout.tie(0);
int T;
cin >> T;
while(T--) {
int N, M;
cin >> N >> M;
if(N == 1) {
cout << M << '\n';
continue;
}
vector<long> dp(M);
for(int i = 0; i < M; i++) {
dp[i] = M-i;
}
for(int i = 2; i < N; i++) {
for(int j = 0; j < M; j++) {
long temp = 0;
for(int k = j+1; k < M; k++) {
temp += dp[k];
}
dp[j] = temp;
}
}
long sum = 0;
for(int i = 1; i < M; i++) {
sum += dp[i];
}
cout << sum << '\n';
}
return 0;
}
Uploaded by Notion2Tistory v1.1.0