문제 이해 단계
https://www.acmicpc.net/problem/1010
N과 M이 주어진다. N <=M이다.
N과 M은 개수를 뜻하며 N과 M을 연결한다.
연결할 때의 규칙
1. N과 M은 각각 한쌍을 이룬다.
2. N과 M을 연결할 때의 선은 서로 겹치면 안 된다.
이 조건일 때, N과 M이 쌍을 이루는 경우의 수를 구하는 문제이다.
문제 접근 단계
일단 예제를 보니까 출력에 터무니없이 큰 숫자가 있었다.
게다가 제한 시간을 보니까 0.5초로 엄청나게 짧았다.
이 점을 미뤄서 생각했을 때, dp로 풀어야 할 것 같아서 dp로 생각해 봤다.
입력값이 n, m 두 개니까 2차원 배열 d [][]가 존재하고
n, m일 때의 경우의 수를 d [n][m]이라고 한다.
만약 d [2][4]를 구한다고 가정해 보자.
d [2][4]를 이전 계산 결과를 활용하여 표현할 수 있을까?
한번 그려보면서 판단해 보면 이렇게 된다.
왼쪽 그림은 d [2][4]에서 나타날 수 있는 경우 중
N에서 첫 번째 수가 M의 1번으로 갈 때, N의 2번째 수가 갈 수 있는 경로이다.
파란색 경로만 따로 떼서 생각해 보면 이는 d [1][3]과 똑같다고 볼 수 있다.
이런 식으로 이전 계산 결과가 남아있다.
그럼 이제 N의 첫 번째 수의 움직임에 따라 모든 경우의 수를 다 더하면 된다.
N의 1번 노드의 움직임에 따라 나타날 수 있는 모든 경우의 수를 나타낸 것이다.
이를 식으로 나타내면 d [2][4] = d [1][3]+d [1][2]+d [1][1]이 된다.
이 법칙은 N과 M이 어떤 숫자가 되던 적용되는데,
1번 노드의 움직임에 따라서 거기에 해당하는 d [][]만 찾아주면 되기 때문이다.
즉 이것은 점화식으로 일반화하면 이렇게 된다.
d [N][M] = d [N-1][M-1]+d [N-1][M-2]+...+d [N-1][M-N-1]
이제 이 점화식을 코드로 구현만 하면 답이 된다.
문제 구현 단계
int N, M;
long long int d[30][30];
long long int dp(int x, int y) {
if (x == 1) return d[x][y] = y;
if (x == y) return d[x][y] = 1;
if (d[x][y]) return d[x][y];
long long int result = 0;
for (int i = y; i >= x; i--) {
result += dp(x - 1, i - 1);
}
d[y - x][y] = result;
return d[x][y] = result;
}핵심이 되는 dp함수이다.
매개변수로 N, M을 뜻하는 x, y를 받는다.
2차원 배열 저장공간 d [][]를 사용하여 해당 경우의 수를 저장해 놓는다.
long long int로 선언한 이유는
값이 엄청나게 커질 수 있기 때문에 오버플로우 발생을 방지하기 위해서이다.
우선 빠른 연산을 위해 N이 1이 경우와
N과 M이 같을 경우는 연산이 쉬우므로 그 결과는 바로 배열에 담아 반환한다.
그리고 이미 연산결과가 있는 경우에는 계산하지 않고 저장된 값을 반환한다.
그리고 dp연산을 시작하여 result에 모두 담아준다.
계산이 끝나면 d [y-x][y]와 d [x][y]에 result를 담아주는데,
이 이유는 해당 문제가 조합으로도 풀 수 있는데
조합의 특성상 두 경우는 답이 같기 때문에 연산 시간을 줄이기 위해 이렇게 해줬다.
해당 문제는 이게 핵심이고 이제 전체코드를 올리고 마무리하겠다.
#include <iostream>
using namespace std;
int N, M;
long long int d[30][30];
long long int dp(int x, int y) {
if (x == 1) return d[x][y] = y;
if (x == y) return d[x][y] = 1;
if (d[x][y]) return d[x][y];
long long int result = 0;
for (int i = y; i >= x; i--) {
result += dp(x - 1, i - 1);
}
d[y - x][y] = result;
return d[x][y] = result;
}
int main() {
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);
int T;
cin >> T;
while (T--) {
int v1, v2;
cin >> v1 >> v2;
cout << dp(v1, v2) << "\n";
}
}
시행착오
dp 너무 어렵다.
다른 알고리즘 문제는 어느 정도 접근할 수 있겠는데 dp는 한번 못 풀면 접근조차 어렵다.
뭔가 해설을 보면 왜 이 생각을 못했지 싶다가도
또 새로운 문제를 보면 머릿속이 텅 비어버린다.
dp적 사고가 아예 안된다. 문제를 많이 풀다 보면 해결될까...?