baekjoon 1520
-
[java] 백준 알고리즘 1520번 내리막 길 풀이알고리즘/백준 알고리즘 2018. 7. 23. 09:44
memoization을 활용한 문제다. 동적계획법에 나오는 유형이라는데 memoization이라는 개념은 이 문제를 풀면서 알게 됐다. 재귀개념까지만 알아서 재귀로 푸니 시간초과. 역시 재귀만 해서는 시간이 많이 걸린다. 원래 계산했던 것을 기억해두고 이전에 했던 계산을 다시 꺼내 줌으로써 반복계산을 피하는 방법이 memoization을 사용하는 방법이다. 이 문제는 이전에 방문했는지를 체크해줄 필요가 없다. 내리막길로 이동한 순간, 다시 오르막으로 올 일이 없기 때문에 이전에 방문했던 곳을 다시 방문할 일이 없다. if문에서 현재 값보다 다음 값이 작아야만 이동하게 만들 것이기 때문에. * 풀이 소스 123456789101112131415161718192021222324252627282930313233..