skeksk91   9년 전

AABBB   

BBAAA 

이고 A가 100점 B가 200점이면

100 100 200 200 200

200 200 100 100 100  

이런 식으로 정수로 배열을 만든 후에 탐색을 하였습니다.

작은예제는 해결가능한데, 제출하면 런타임 오류 뜨군요 ㅠ 

10^6 만큼 재귀호출하는데 스택오버플로가 난건가요? 

아니면 pruning을 해야하는 그런 문제인가요.

아니면 아예 다른 방식이 필요한가요 아니면 반복문으로도 해결?그건 좀 어렵겠는데 ㅠ

요번 연습대회때 이것만 10번넘게 고치다가 ㅋㅋㅋ 시간 다갔네요 ㅠㅠ

h0ngjun7   9년 전

10^6 만큼만 재귀호출이 되지 않습니다.

dfs 탐색 시, 가중치가 큰 것부터 먼저 탐색했다면 나중에 가중치가 작은 것으로 다시 탐색해주어야하므로 exponential할 것으로 생각됩니다.

다익스트라를 돌리듯이 현재까지 방문한 grid의 집합(4방향으로 다 이웃한 하나의 집합이겠죠?) 중 새로 추가되는 집합의 원소로서 그 가중치가 가장 작은 걸 계속 넣어준다면 O(n^2 log n)에 풀 수 있습니다.

등장하는 알파벳의 개수가 25개('E'를 제외하고)이므로, 잘 생각해보면 O(n^2 * 25)에도 풀 수 있을 것 같습니다.

pichulia   9년 전

그리고 런타임 에러가 발생한 이유는 

재귀호출하는 함수 안에 있는 dr[4][2]배열 때문에

메모리초과가 뜬 것입니다.

이 배열을 밖으로 빼주면 런타임에러가 나지 않고

무사히 틀렸습니다를 받습니다.

그리고 dfs로 답이 나오지 않는 예제를 하나 쓰면

4 3

999 999 999 999

999 4 E 999

999 1 4 999

이런 데이터가 있을 때

답은 4가 나와야 하지만

현재 코드론 9가 나옵니다.

현재 코드에서 어떻게 고쳐야 할지는 잘 모르겠고...dfs로 풀면 안될것같다는 의견만 남기겠습니다.ㅠㅠㅠ

skeksk91   9년 전

아하... 
바보같이 한번 탐색한것을 캐시에 넣고 그걸 최적으로 풀었네요 ㅠㅠ. 이 실수가 반복되네.. 

홍준아 알려줘서 고맙구  pichulia님 예시 감사합니다 ㅎ.ㅎ

동적계획법으로 [1000][1000][sum] 까지 하긴 메모리가 안되니깐

말대로 bfs로 풀어야겠다 ㅋㅋㅋㅋㅋ 한 수 알려주셔서 고맙습니다 다들 

skeksk91   9년 전

dr[4][2] 지적 감사합니다 후아 속이 뻥뚫리네요 

다음부터 신경써야겠요 후후 ㅋㅋㅋ

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