jh1125kr   1년 전

스택을 이용하여 미로찾기 문제 형식으로 풀었습니다

구조체 사용하여 처음에 east(오른쪽), south(아래)를 1로 선언하고 distance에는 현재점에서 갈수있는 거리를 넣어줬습니다.

방문하면 0으로 고쳐줬습니다. 그리고 조건에 부합하면(현재점에서 갈수있는 거리+현재 index가 n-1의 배열 범위를 벗어나지 않으면)

스택에 넣어줬습니다.

몇개의 테스트 케이스를 해보아도 다 맞는것 같은데 어디서 틀렸는지 모르겠습니다..ㅠㅠ


yukariko   1년 전

이 소스는 한 번 방문하고 나면 그쪽으론 다시 안가게 끔 구현된것 같은데

그렇게 하려면 그 방향으로 방문했을때의 정답을 계산을 하고, 다음 다시 그쪽을 방문시 계산한 값을 내놓는

흔히 말하는 dp 형식을 띄고 있어야 합니다.

이 소스는 그냥 n-1, n-1에 도착하면 ans 값을 1씩 증가하는것이라

답이 틀리게 됩니다.

맞다고 해도 답이 2^63 근처까지 갈 수 있기 때문에 시간초과를 받게될 것 같군요..

dp와 재귀를 사용하면 간단하게 풀 수 있는 문제입니다.

jh1125kr   1년 전

아 그렇군요...ㅠㅠ답변 감사합니다 dp로 다시풀어야겠네요ㅠㅠ

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