1520번: 내리막 길
여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으
www.acmicpc.net
5557번: 1학년
상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀
www.acmicpc.net
오늘 nts 코테가 있던 날이었다.
정확히 어떤 문제인지는 복기하지 않겠으나, dfs + dp 로 푸는 문제였는데,
전날에 1학년 문제를 풀었음에도 불구하고 막상 가니까 구현이 안되서 정확도 점수만 받았다 (...)
그래서 내리막 길 이라는 문제도 풀어봤는데, 구현 방법에서 사소한 차이가 있었고, 그게 굉장히 크리티컬한 역할을 하게 됨을 알았다. 이 글을 쓴 이유이기도 하다.
5557번 1학년 코드 (C++)
#include<cstdio>
using namespace std;
int T;
int num[101];
long long dp[101][21]; // 경우의 수 저장
long long dfs(int n, int k) {
if (n == T-1) {
if (num[T - 1] == k) return 1;
else return 0;
}
if (dp[n][k]) return dp[n][k];
if (k + num[n] <= 20) dp[n][k] += dfs(n + 1, k + num[n]);
if (k - num[n] >= 0) dp[n][k] += dfs(n + 1, k - num[n]);
return dp[n][k];
}
int main() {
scanf("%d", &T);
for (int i = 0; i < T; i++) {
scanf("%d", &num[i]);
}
dp[0][num[0]] = 1;
printf("%lld", dfs(1, num[0]));
return 0;
}
보면 흔한 dfs + 메모이제이션 조합이다.
이 문제를 풀 때는 0 을 딱히 고려하지 않았는데 시간초과가 나지 않았다.
왜냐하면 왼쪽에서 순서대로 계속 덧셈/뺄셈을 시행했을때 항상 0 이상 20 이하 임이 보장되어야 한다는 조건이 있기 때문이다. 그래서 많은 경우의 수가 가지치기 되기 때문에 시간초과가 나지 않았던 것. (추측임)
만약 저 값의 범위가 더 커지면 시간초과가 날 수 있지 않을까? 생각해 봤다. 경우의 수도 그만큼 커지겠지만.
1520번 내리막 길 코드 (C++)
#include<cstdio>
#include<cstring>
using namespace std;
int N, M;
int map[501][501];
int dp[501][501]; // 경우의 수 저장
int dfs(int n, int m, int val) {
if (n == N && m == M) return 1;
if (dp[n][m] != -1) return dp[n][m];
dp[n][m] = 0; // 핵심
if (n + 1 <= N && val > map[n + 1][m]) {
dp[n][m] += dfs(n + 1, m, map[n + 1][m]);
}
if (n - 1 >= 1 && val > map[n - 1][m]) {
dp[n][m] += dfs(n - 1, m, map[n - 1][m]);
}
if (m+1 <= M && val > map[n][m + 1]) {
dp[n][m] += dfs(n, m + 1, map[n][m+1]);
}
if (m - 1 >= 1 && val > map[n][m - 1]) {
dp[n][m] += dfs(n, m - 1, map[n][m - 1]);
}
return dp[n][m];
}
int main() {
scanf("%d %d", &N, &M);
for (int i = 1; i <= N; i++) {
for(int j = 1; j <= M; j++)
scanf("%d", &map[i][j]);
}
memset(dp, -1, sizeof(dp));
printf("%d", dfs(1,1,map[1][1]));
return 0;
}맨 처음부터 찾든 맨 뒤부터(N,M 부터) 찾든 상관이 없다. 제목은 내리막 길인데 방향은 내리막 길이 아니거든.
4방향으로 모두 갈 수 있다. 처음에 제목 보고 헷갈려서 위로 진행하는 코드를 안 넣고 틀렸다.
위 코드에서 N, M 은 헷갈려서 그냥 내가 임의로 맞바꾼거다. C 는 row-major 니까 😜
여튼, 각설하고 이 경우에는 처음에 위의 코드를 거의 그대로 갖다 썼더니 시간초과가 났다.
이유인 즉슨, 아까는 0이 있든 말든 크리티컬한 요소는 아니었다. 거기가 0개라고 해서 더 찾아들어갈 요인이 없거든. 어차피 가는 길에 0이 있다는 얘기는 + - 연산하면서 0 ~ 20 범위를 넘겨 뒤에서 금방 짤릴 놈들이라는 뜻이다. ( = 다시말해서, 대충 + - + - + - ... 로 0 ~ 20 범위 내에서 아슬아슬하게 줄타기하는 식이 존재할 가능성이 높음을 고려했을 때, dp 배열의 대부분은 1 이상일 것이다.) 아님 테스트셋의 문제일수도
하지만 여기선 0일 경우 4 방향으로 모두 탐색하게 된다. 어차피 높이 조건 때문에 돌고 돌고 무한루프 탈일은 없겠지만, 메모이제이션이 의미 없어진다는 점.
그래서 메모이제이션을 유의미하게 만들기 위해, dp 를 -1로 설정한다. 이제 -1이 not visited 를 의미하는 것이다. 대신에 내가 주석에 '핵심' 이라고 적어놓은 것을 보자. 해당 칸을 방문했을 땐 꼭 0으로 초기화를 해줘야한다. (안그럼 -1 이 누적되는 대참사가 난다.😢 ) 어쨌든 방문 안했으면 아무 것도 안 더해야 되니깐.
그러면 시간초과가 사라지고 문제가 풀린다.
어, 그럼 생각해보니 1학년 문제도 사실 주저리주저리 합리화 하긴 했지만, 똑같이 풀 수 있다는 거 아닌가? 큰 의미는 없을지라도 한 번 개선을 해보자.
5557 1학년 코드 (C++) 개선한 버젼
#include<cstdio>
#include<cstring>
using namespace std;
int T;
int num[101];
long long dp[101][21]; // 경우의 수 저장
long long dfs(int n, int k) {
if (n == T-1) {
if (num[T - 1] == k) return 1;
else return 0;
}
if (dp[n][k] != -1) return dp[n][k];
dp[n][k] = 0;
if (k + num[n] <= 20) dp[n][k] += dfs(n + 1, k + num[n]);
if (k - num[n] >= 0) dp[n][k] += dfs(n + 1, k - num[n]);
return dp[n][k];
}
int main() {
scanf("%d", &T);
for (int i = 0; i < T; i++) {
scanf("%d", &num[i]);
}
memset(dp, -1, sizeof(dp));
dp[0][num[0]] = 1;
printf("%lld", dfs(1, num[0]));
return 0;
}개선해도 시간 차이가 크진 않을 것이다. 특히 앞에서 얘기한 그 가정에 따르면 길이가 길어질 수록 그 차이가 더 줄어들 것으로 예상된다. 하지만 최적화 관점에선 이게 더 나을 수도 있다는 생각을 해봤다. (memset 하는 시간이 있긴 하지만 주소에 한 번에 접근해서 엄청 빠르다고 알고 있다.)
끗.