목록코딩 (1)

계단을 오르듯이

1520. 내리막 길

평소처럼 dfs/bfs로 풀었지만 시.간.초.과.. 500 * 500 이라서 될 줄 알았지만, 모든 인덱스 위치에서 모든 경우를 다 계산해야 하기에 최대 500 * 500마다 500 * 500이 될 수 있으므로 250000 * 250000 가 되어 시간초과가 당연히 발생되는 것이다. 시간을 줄이고자 방문해서 도착지점에 도착했던 경로는 당연히 나중에도 그 길을 통해 도착이 보장되므로 그 길을 다시 확인하는 수를 줄여야겠다고 생각했다. dfs의 return값을 통해 방문과 함께 갈 수 있는 길의 수를 구하기 위해 dp와 dfs를 함께 이용해 풀었다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647pack..
알고리즘/백준_JAVA 2022. 1. 10. 07:29
이전 Prev 1 Next 다음