1463번 - 1로 만들기
왜인지 머리가 안 돌아가서 동적계획법이 정해인 문제임에도 재귀로 풀었고, 다행히도 Python 으로도 메모리/시간 제한에 걸리지 않고 잘 풀리는것을 확인했습니다. 다행히 재귀 depth 가 생각보다 깊지 않아서 어찌저찌 됐습니다. 다만 재귀가 돌다보니 당연히 램/수행시간 모두 좋지 않습니다. PyPy3 탓도 있겠지만.
https://www.acmicpc.net/source...
보니까 이 문제에 대해서 DP와 BFS 중 어느쪽을 써도 풀린다는 이야기가 있는데, 이거 보고 제 나중의 학습을 위해 정리합니다.
다른 분들의 DP 해법은 대충 알겠습니다.
이런게 DP 해법이군요. (스포일러 방지를 위해 구체적인 구현은 이 글에서 설명하지 않겠습니다)
같은 방식으로 BFS로 구현해둔것도 찾아보니 있긴 합니다.
성능도 BFS가 압도적으로 빠르네요. 과연...
댓글을 작성하려면 로그인해야 합니다.
dhunter 2년 전
왜인지 머리가 안 돌아가서 동적계획법이 정해인 문제임에도 재귀로 풀었고, 다행히도 Python 으로도 메모리/시간 제한에 걸리지 않고 잘 풀리는것을 확인했습니다. 다행히 재귀 depth 가 생각보다 깊지 않아서 어찌저찌 됐습니다. 다만 재귀가 돌다보니 당연히 램/수행시간 모두 좋지 않습니다. PyPy3 탓도 있겠지만.
https://www.acmicpc.net/source...
보니까 이 문제에 대해서 DP와 BFS 중 어느쪽을 써도 풀린다는 이야기가 있는데, 이거 보고 제 나중의 학습을 위해 정리합니다.
다른 분들의 DP 해법은 대충 알겠습니다.
https://www.acmicpc.net/source...
이런게 DP 해법이군요. (스포일러 방지를 위해 구체적인 구현은 이 글에서 설명하지 않겠습니다)
같은 방식으로 BFS로 구현해둔것도 찾아보니 있긴 합니다.
https://www.acmicpc.net/source...
성능도 BFS가 압도적으로 빠르네요. 과연...