| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 16 MB | 2060 | 521 | 411 | 26.933% |
문제
세준이가 살고 있는 도시는 신기하게 생겼다. 이 도시는 격자형태로 생겼고, 직사각형이다. 도시의 가로 크기는 N이고, 세로 크기는 M이다. 또, 세준이의 집은 (0, 0)에 있고, 세준이의 학교는 (N, M)에 있다.
따라서, 아래 그림과 같이 생겼다.
세준이는 집에서 학교로 가는 길의 경우의 수가 총 몇 개가 있는지 궁금해지기 시작했다.
세준이는 항상 최단거리로만 가기 때문에, 항상 도로를 정확하게 N + M개 거친다. 하지만, 최근 들어 이 도시의 도로가 부실공사 의혹으로 공사중인 곳이 있다. 도로가 공사 중일 때는, 이 도로를 지날 수 없다.
(0, 0)에서 (N, M)까지 가는 서로 다른 경로의 경우의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 도로의 가로 크기 N과 세로 크기 M이 주어진다. N과 M은 100보다 작거나 같은 자연수이고, 둘째 줄에는 공사중인 도로의 개수 K가 주어진다. K는 0보다 크거나 같고, 100보다 작거나 같은 자연수이다. 셋째 줄부터 K개 줄에는 공사중인 도로의 정보가 a b c d와 같이 주어진다. a와 c는 0보다 크거나 같고, N보다 작거나 같은 자연수이고, b와 d는 0보다 크거나 같고, M보다 작거나 같은 자연수이다. 그리고, (a, b)와 (c, d)의 거리는 항상 1이다.
출력
첫째 줄에 (0, 0)에서 (N, M)까지 가는 경우의 수를 출력한다. 이 값은 0보다 크거나 같고, 2^63-1보다 작거나 같은 자연수이다.
접근
table[i][j] = table[i - 1][j] + table[i][j - 1] 이란 식이 나오는 아주 간단한 DP 문제이다.
하지만 공사중인 길을 어떻게 표현할 것인가가 핵심이다.
나는 각 좌표마다 2개의 값을 갖는 배열을 만들고,
첫번째 인덱스를 위 세로줄이 연결되었는지,
두번째 인덱스를 오른쪽 가로줄이 연결되었는지로 놓았다.
이 배열을 이용하면 손쉽게 예외처리를 할 수 있다.
풀이
처음에 가로, 세로를 거꾸로 봐서 반대로 입력받았다.
a, b, c, d를 입력받을 때 (a, b)를 더 작은 좌표로 바꿨다.
그리고 a == c 를 통해 가로줄인지 세로줄인지 확인했다.
이후 점화식을 순차적으로 채우면 된다.
끝 값의 예외처리만 주의해주면 된다.
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define FUP(i, a, b) for(int i = a; i <= b; i++)
#define FDOWN(i, a, b) for(int i = a; i >= b; i--)
#define MS(a, b) memset(a, b, sizeof(a))
#define ALL(v) v.begin(), v.end()
#define CIN(a) cin >> a;
#define CIN2(a, b) cin >> a >> b
#define CIN3(a, b, c) cin >> a >> b >> c
#define COUT(a) cout << a
#define COUT2(a, b) cout << a << ' ' << b
#define COUT3(a, b, c) cout << a << ' ' << b << ' ' << c
#define ENDL cout << '\n'
int dy[4] = { -1, 1, 0, 0 };
int dx[4] = { 0, 0, 1, -1 };
ll N, M, K, arr[101][101][2], dp[101][101];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
MS(dp, 0);
MS(arr, 0);
CIN3(M, N, K);
while (K--)
{
int a, b, c, d;
CIN2(b, a);
CIN2(d, c);
if (a > c) swap(a, c);
if (b > d) swap(b, d);
arr[a][b][a == c] = 1; // 가로 1, 세로 0
}
dp[0][0] = 1;
FUP(i, 0, N)
{
FUP(j, 0, M)
{
if (j != M && !arr[i][j][1]) dp[i][j + 1] += dp[i][j];
if (i != N && !arr[i][j][0]) dp[i + 1][j] += dp[i][j];
}
}
COUT(dp[N][M]);
return 0;
}여담
숏코딩 1등했다.
