문제를 이해하는 것이 우선이였다. 내가 위치하는 곳의 값만큼 오른쪽이나 아래로 이동할 수 있다는 것이다.
동적 프로그래밍을 이용해 풀었는데, dp[i][j]에 (i, j)로 왔을 때 경로의 수를 저장하였다.
주황색 부분을 검사하는 코드가 다음과 같다. 주황색 부분을 돌면서, 주황색 부분에 든 숫자 arr[][]와 주황색과 [i][j]까지의 거리가 같다면, 주황색에서 [i][j]로 이동할 수 있다는 것을 알게 된다. 따라서, dp[i][j] += dp[k][j];를 해주면, 주황색 부분까지 가는 경우의 수를 더해준다는 의미가 되겠다.
for (int k = 1; k < i; k++) {
if (arr[k][j] == i - k) {
dp[i][j] += dp[k][j];
}
}
초록색 부분을 검사하는 코드가 다음과 같다. 초록색 부분을 돌면서, 주황색 부분에 든 숫자 arr[][]와 초록색과 [i][j]까지의 거리가 같다면, 초록색에서 [i][j]로 이동할 수 있다는 것을 알게 된다. 따라서, dp[i][j] += dp[i][k];를 해주면, 초록색 부분까지 가는 경우의 수를 더해준다는 의미가 되겠다.
for (int k = 1; k < j; k++) {
if (arr[i][k] == j - k) {
dp[i][j] += dp[i][k];
}
}
코드
#include <bits/stdc++.h>
using namespace std;
int n;
long long arr[101][101], dp[101][101];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> n;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> arr[i][j];
}
}
dp[1][1] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
for (int k = 1; k < i; k++) {
if (arr[k][j] == i - k) {
dp[i][j] += dp[k][j];
}
}
for (int k = 1; k < j; k++) {
if (arr[i][k] == j - k) {
dp[i][j] += dp[i][k];
}
}
}
}
cout << dp[n][n];
}
dp[i][j]에는 (i, j)까지 탐색했을 때 가장 많은 사탕을 받을 수 있을 때, 가지고 있는 사탕의 수를 저장한다.
준규는 (r, c)에 있으면, (r+1, c), (r, c+1), (r+1, c+1)로 갈 수 있으므로 위쪽 왼쪽부터 아래쪽 오른쪽 순서로 dp 탐색을 하면 될 것 같다. dp[i - 1][j] + arr[i][j], dp[i - 1][j - 1] + arr[i][j], dp[i][j - 1] + arr[i][j] 중에서 dp[i][j]에 가장 큰 값을 저장하면 된다.
코드
#include <bits/stdc++.h>
using namespace std;
int n, m, arr[1001][1001], dp[1001][1001];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> arr[i][j];
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
dp[i][j] = max(dp[i][j], dp[i - 1][j - 1]);
dp[i][j] += arr[i][j];
}
}
cout << dp[n][m];
}
백 트래킹 방식으로 해결하고자 했다. 스도쿠 빈 칸에 1부터 9까지 숫자를 넣고, 그 숫자가 promising한지 검사 후, promising하다면 스도쿠의 답으로 인정하고, promising하지 않다면 다음 숫자를 검사하거나, 모든 숫자를 검사했다면 그 전 백 트래킹 함수로 돌아가 다른 답을 찾는다.
빈 칸을 기억하고 있는 vector<pair<int, int>> zero;를 선언하였고, 그 벡터의 크기인 zeroNum을 저장해 두었다.
함수 bt의 파라미터는 벡터 zero에서 indexlevel까지 답을 찾았다 라는 의미다. 따라서, bt가 멈추는 조건도 if(level == zeroNum - 1)라고 정의할 수 있겠다. if(level == zeroNum - 1)이면 zero에 들어있던 모든 빈칸에 대한 답을 찾은 것 이므로, print해주고 exit(0)해주면 된다. 문제의 조건이 여러 답 중에 하나만 출력하면 되므로 제일 먼저 찾은 것을 출력했다.
