[SWEA] 1949. 등산로 조성

문제 링크: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PoOKKAPIDFAUq

 

2019년 12월 27일 2시 30분부터 2문제 (등산로 조성과 수영장 문제)를 시도해보았습니다. 이번에 선택된 문제들은 상대적으로 쉬운 문제들이라 5시가 되기 전에 풀 수 있었습니다. 

 

 이번 문제도 아주 전형적인 dfs라고 볼 수 있습니다. 가장 높은 곳에서 시작하여 만들 수 있는 등산로중 가장 긴 등산로를 찾는 것이 문제입니다. 또 하나의 특징은 한 지점을 선택하여 최대 k만큼 산을 깎을 수 있다는 것입니다. 물론 깎지 않아도 무방합니다. 저는 무식한 방법을 택했습니다. 모든 지점을 0~k만큼 깎아보고 가장 높은 지점에서 시작하여 dfs로 가장 긴 등산로를 찾는 방법입니다. 가장 높은 지점은 최대 5곳이고 최대 k는 5이므로 시간 복잡도는 5 * 64 * 6 * O(dfs)입니다. 맵의 크기가 크지 않아 dfs에 오래 걸리지 않을 것이라고 판단하고 제출하였습니다.

 

 하지만 다른 제출 코드에 비해 많이 느리더군요. 빠르면 6 ~7ms 정도 걸리지만 제 코드는 100ms가 넘습니다. 좀 더 시간 단축을 시킬 수 있는 여지가 있는 것 같습니다. 다른 분들의 코드를 분석하여 추가적인 내용을 업로드하겠습니다.