문제
세준이는 크기가 N*M인 직사각형 도시에 살고 있다. 또, 세준이의 집은 (1, 1)에 있고, 학원은 (N, M)에 있고, 오락실이 C개 있다.
세준이의 현재 위치가 (r, c) 일 때, (r+1, c) 또는 (r, c+1)로만 이동할 수 있다. 오락실을 방문할 때는 규칙이 하나 있는데, 오락실 번호가 증가하는 순서대로 가야 한다는 것이다. 2번 오락실을 먼저 가고, 그 후에 1번 오락실을 가면 안 되고, 2번 오락실을 가려면, 그전에 아무 오락실도 가지 않거나, 1번 오락실을 방문했을 때만 가능하다.
세준이는 오락실을 K번 방문해서 학원에서 도착하는 경로의 경우의 수가 궁금해지기 시작했다. 오락실을 0개 방문했을 때부터, C개 방문했을 때 까지 경우의 수를 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 N M C가 주어진다. N과 M은 50보다 작거나 같은 자연수이고, C는 50보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 C개의 줄에 1번 오락실부터 C번 오락실까지 위치가 차례대로 주어진다. 오락실의 위치가 중복되는 경우는 없지만, 오락실의 위치가 (1,1) 또는 (N, M) 일 수도 있다.
출력
첫째 줄에 0개 방문했을 때, 1개 방문했을 때, ..., C개 방문했을 때 총경로의 개수를 한 줄에 공백을 사이에 두고 출력한다. 경로의 개수는 1,000,007로 나눈 나머지를 출력한다.
🔎문제 해석
- 출발점은 항상 (1,1)으로 고정, 우리는 (n,m)까지 도달해야 한다.
- 여기서 쟁점은 오락실의 개수를 정해놓고, 그 개수만큼 방문하는 경로의 수를 찾아야 한다.
- 오락실은 좌표와 오락실 번호가 주어진다.
- 이것은 map을 통해서 좌표와 오락실 번호를 저장했다.
- map<pair<int,int>,int>>
- key : 좌표 x, 좌표 y / value : 오락실넘버
DP알고리즘을 사용해서 풀었다.
DP 배열은 4차원 배열로
DP [x좌표][y좌표][방문한 오락실의 최대 번호][방문한 오락실의 개수]로 구성했다.
4차원 배열을 써도 되는 이유는 x좌표와 y좌표, 오락실의 개수가 50개로 제한되었기 때문에 메모리 제한을 크게 잡아먹지 않는다
DP를 풀면 하듯이 첫 출발점에 값을 1로 세팅해 놓는다.
근데 여기서 출발점이 오락실에 해당할 수 있으므로,
만약 출발점이 오락실이라면 값을 바꿔줘야 한다.
초기 설정은 DP [1][1][0][0] = 1이다.
근데 만약 출발점이 (1,1)이라면 DP [1][1][오락실번호][1] = 1로 바꿔줘야 한다.
이제 탐색을 시작한다.
이동한 좌표가 오락실이라면 해당 오락실번호만큼 반복문을 돌려서 이동한 좌표까지의 모든 경로를 합쳐준다.
만약 이동한 좌표가 오락실이 아니라면, 위와 왼쪽 경로의 값들을 더해준다.
🖥️코드
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
int n, m, c;
int DP[51][51][51][51]; // 형, 열, 오락실최대번호, 오락실개수
map<pair<int, int>, int> M;
int graph[51][51];
int graphnumber[51][51];
int mod = 1000007;
void funct();
int main()
{
cin >> n >> m >> c;
int trow, tcol;
DP[1][1][0][0] = 1;
for (int i = 1; i <= c; i++)
{
cin >> trow >> tcol;
if (trow == 1 && tcol == 1)
{
DP[1][1][i][1] = 1;
DP[1][1][0][0] = 0;
}
M.insert(make_pair(make_pair(trow, tcol), i));
}
funct();
for (int i = 0; i <= c; i++)
{ // 오락실 수.
int sum = 0;
for (int j = 0; j <= c; j++)
{ // 오락실 번호
sum += DP[n][m][j][i];
sum %= mod;
}
sum %= mod;
cout << sum << "\n ";
}
}
void funct()
{
for (int i = 1; i <= n; i++)
{ // DP[행][열][오락실수][오락실넘버]
for (int j = 1; j <= m; j++)
{
if (i == 1 && j == 1)
{ // 출발점.
continue;
}
if (M.find(make_pair(i, j)) != M.end()) // 만약 이곳이 오락실이라면?
{
int key = M.find(make_pair(i, j))->second; // 벙문한 오락실 넘버
for (int k = 0; k < key; k++)
{ // 오락실넘버.
for (int x = 0; x <= k; x++)
{ // 방문 갯수. 현재 오락실넘버 만큼 오락실을 방문할 수 있다.
DP[i][j][key][x + 1] += DP[i - 1][j][k][x] + DP[i][j - 1][k][x];
DP[i][j][key][x + 1] %= mod;
}
}
}
else //오락실이 아닐 경우
{
for (int l = 0; l <= c; l++)
{
for (int k = 0; k <= l; k++)
{
DP[i][j][l][k] = DP[i - 1][j][l][k] + DP[i][j - 1][l][k];
DP[i][j][l][k] %= mod;
}
}
}
}
}
}
😃느낀 점
- 우선 각 경로마다 오락실의 최고 번호와 방문한 오락실의 개수를 저장하기 위해서 많은 시도를 해봤지만,
4차원배열이 제일 깔끔한 방법이었다. (문제에서 주어진 배열 크기가 크지 않아서이다.)- 만약 배열의 크기가 좀 더 큰 수였다면 4차원 배열은 어림도 없을 것 같다.
- 지금 와서 다시 코드를 보니 굳이 map을 사용해야 했나 싶기도,,? 그냥 2차원 배열에 오락실 넘버를 저장해도 될 것 같다.
- 값이 커서 계속 특정한 숫자로 나누는 이러한 문제들을 자주 풀어보는데, 그냥 더하는 과정에서 모두 나눠주는 게 맞는 것 같다.
- 4차원 배열에 대한 접근 때문에 골드 2라는 난이도가 주어진 것 같다.
'CodingTest > Baekjoon' 카테고리의 다른 글
[백준 1976] - 여행가자(C++)[골드4] (0) | 2023.03.04 |
---|---|
[백준 5427] - 불(C++)[골드4] (0) | 2023.03.02 |
[백준 5972] - 택배배송(C++)[골드5] (0) | 2023.02.26 |
[백준 14891] - 톱니바퀴(C++)[골드5] (2) | 2023.01.17 |
[백준 12869] - 뮤탈리스크(C++)[골드4] (0) | 2023.01.15 |