petil777   1년 전

제 방법대로 하면 같은 의미를 나타내는게 2번호출되어 실제 경우의 수보다 2배커지게 됩니다

처음에 cache로 메모를 할때 0으로 했더니 30%까지 가고 시간초과가 발생해서 고민해보니 이미 불가능해서 0가지로 확정된 경우를 cache가 기본적으로 0이다 보니까 구분이 안가서 불가능한 경우를 반복해서 세게 된다는 걸 알게됐습니다.

그래서 cache를 -1로 초기화하고 조사를 할 때 마다 0으로 세팅해서 한번 불가능 확정된 경우를 다시 보지 않게 하였더니 바로 틀렸습니다...(30%Accept된 코드와 여러개 예시를 만들어 넣어서 비교해봤는데 제가 넣어본 것은 모두 일치하더군요..)

따라서 제 알고리즘 논리에서 어느 부분이 잘못됐는지 알고 싶습니다.

참고로 dfs과정에서 혹시 수 범위를 벗어나지 않을까 하여 500개 발판이 있고 모두 서로 왔다갔다 할 수 있는 최악의 경우를 고려했을 때 unsigned long long으로 터지지 않아서 괜찮다고 판단했습니다.

그리고 이 방법이 잘못됐다면 보다 효율적으로 짤 수 있는 방법(점화식)힌트 좀 주세요 ㅠ.ㅠ

baekjoon   1년 전

방법이 맞긴 한데, 조금 고치면 될 것 같네요.

참고로 문제에서 1000으로 나눈 나머지를 출력하라는 경우는, int나 long long 의 범위를 넘어갈 수 있기 때문입니다.

https://www.acmicpc.net/problem/10430

이 문제를 풀어보면, 어떻게 고쳐야하는지 알 수 있습니다. 그리고, 위의 문제만 고친다고 해서 정답이 되지는 않습니다.

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