wjdwldud4190   7년 전

런타임 에러가 발생했었는데ㅠㅠ 도움 주셔서 고쳤습니다ㅜㅜ 감사합니다. 

그런데 시간초과가 나서요.. 제가 아직 시간계산은 잘 못해서 어느 부분에서 나는지 감이 안와서요..

혹시 보시고 감이 오시는 분이 계시다면 가르쳐 주시면 정말 감사합니다ㅠㅠ 제 힘으로 해볼려고 했는데 안되네요.. 몇일 째 잡고있는데..ㅜㅜ 

귀한 시간내주셔서 감사합니다!!

uk7880   7년 전

제 기억으론 이문제 알고리즘 분류가 BFS라고 되어있지만 BFS로할 경우 시간 초과가 나서

DP로 풀어야했던걸로 기억합니다.....

시간계산은 다른 고수분들이 적어주실거라믿고 ... 20000...

wjdwldud4190   7년 전


@uk7880

답변 너무 감사합니다ㅠㅠ 그런데 한가지만 더 여쭤봐도 될까요.. dp라면 메모리제이션을 해야하는데 

이 문제 같은 경우 답을 찾을 때 같은 경로를 여러번 가게 됩니다. 그래서 저는 메모리제이션이 아닐거라 생각했습니다..그런데 다시 생각해보니

겹치는 좌표들을 메모리제이션 하면 될까요..? 알고리즘의 길은 멀고도 머네요!ㅜㅜ

uk7880   7년 전

같은 경로를 여러번 가게 되지만 그 x,y좌표에 몇번째에 도달했는지는 다르지않을까요?

(1,1) -> (1,2) -> (1,1) -> (1,2)가 먼저 구해지고

(2,2) -> (2,1) -> (1,1) -> (1,2)를 구한다면 3번째만에 도착한(1,1)은 이미 계산이 되어있을겁니다.

설명이 서툴러서 제대로 이해하실지 모르겠네요 ㅠㅠ.....

wjdwldud4190   7년 전

@uk7880
감사합니다ㅠㅠ 답변해주신 내용을 가지고 더 고민해보겠습니다. 정말 감사합니다.

wjdwldud4190   7년 전

@uk7880


해결했습니다.. 정말 감사합니다. 개운하네요ㅠㅠ

uk7880   7년 전

조잡한 설명으로 문제푸셔서 감사할따름입니다ㅜㅜ

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