반응형
진우의 달 여행 (Large)
-
[백준] 17485 진우의 달 여행 (Large) with PythonPS 2022. 6. 4. 01:03
📌 BOJ 17485 진우의 달 여행 (Large) 💡 조건 지구와 우주사이는 N X M 행렬로 나타낼 수 있으며 각 원소의 값은 우주선이 그 공간을 지날 때 소모되는 연료의 양이다. N, M (2 ≤ N, M ≤ 1000), 각 행렬의 원소값은 100 이하의 자연수이다. 지구 -> 달로 가는 경우 우주선이 움직일 수 있는 방향은 아래와 같다. 우주선은 전에 움직인 방향으로 움직일 수 없다. 즉, 같은 방향으로 두번 연속으로 움직일 수 없다. 진우의 목표는 연료를 최대한 아끼며 지구의 어느위치에서든 출발하여 달의 어느위치든 착륙하는 것이다. 최대한 돈을 아끼고 살아서 달에 도착하고 싶은 진우를 위해 달에 도달하기 위해 필요한 연료의 최소값을 계산하는 문제 다이나믹 프로그래밍, 완전탐색 유형의 문제 🖥 소..