글 읽기 - 약 80퍼 쯤에서 틀렸습니다.

zpapl 6년 전 0

처음에 DFS로 접근을 하니 시간초과가 났습니다.

그래서 BFS로 접근을 하니 메모리 초과가 났습니다.

그래서 DFS + DP로 접근을 했습니다.

처음에는 런타임 에러가 발생하고 TC를 찾아보니

중간에 0이 있는 경우를 처리 안해서 무한루프가 발생해서 처리했습니다

이제는 80퍼센트에서 그냥 틀렸습니다가 나옵니다.

아!! 중간에 경우의 수가 32비트로 부족하다는 걸 알아서 long long을 썻는데 안됩니다..

무엇이 문제일가요?

​<소스>

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int N;
vector<vector<int>> adj;
vector<vector<long long>> dp;

int dfs(int y, int x) {
if (y == N - 1 && x == N - 1) {
return 1;
}

if (dp[y][x] != -1) {
return dp[y][x];
}

dp[y][x] = 0;

int downY = y + adj[y][x], downX = x;
int rightY = y, rightX = x + adj[y][x];

if (downY >= 0 && downY < N && downX >= 0 && downX < N) dp[y][x] += dfs(downY, downX);
if (rightY >= 0 && rightY < N && rightX >= 0 && rightX < N) dp[y][x] += dfs(rightY, rightX);

return dp[y][x];
}

int main() {
cin >> N;

adj = vector<vector<int>>(N, vector<int>(N, 0));
dp = vector<vector<long long>>(N, vector< long long>(N, -1));

for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cin >> adj[i][j];
}
}

cout << dfs(0, 0) << endl;
}

sgchoi5 6년 전 0

BOI 문제는 대회에서 사용한 TC 가 공개되어 있으니 받아서 한 번 해보셔요.

http://gooddaytocode.blogspot....

zpapl 6년 전 0

TC를 확인해 봤습니다.

그런데 출력이 long long이 표현할 수 있는 값 보다 크게 나오는데...이런 경우에는 어떻게 처리할 수 있을까요??

unsigned long long 보다도 큽니다..

sgchoi5 6년 전 0

답은 long long 으로 처리가능했습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

약 80퍼 쯤에서 틀렸습니다.

zpapl 6년 전 0

sgchoi5 6년 전 0

zpapl 6년 전 0

sgchoi5 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말