728x90 동적프로그래밍2 [BOJ/Python] 2579. 계단 오르기 📌 문제 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 📌 문제 접근 방법 첫 번째 칸을 밟는 경우, 최대값은 첫 번째 칸의 점수 두 번째 칸을 밟는 경우, 최대값은 첫 번째 칸 + 두 번째 칸의 점수 세 번째 칸을 밟는 경우, 첫 번째 칸 + (2칸 이동) 세 번째 칸 두 번째 칸 + (1칸 이동) 세 번째 칸 i번째 칸을 밟는 경우, i-3번째 칸 + (2칸 이동) i-1번째 칸 + (1칸 이동) i번째 칸 i-2번째 칸 + (1칸 이동) i번째 칸 .. 2021. 10. 8. [BOJ/Python] 1520. 내리막 길 📌 문제 https://www.acmicpc.net/problem/1520 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net 📌 문제 접근 방법 이것저것 내 생각으로 할 수 있는 모든 시도를 다 해본 것 같다! (그냥 dfs, 방문 체크 리스트를 아예 가지고 다니기 등등) 결국 포기하고 구글링..! dp를 활용해야 하는 문제였다. 출발점에서 시작해서 도착점까지 도달할 수 있다면, dp 리스트에 값을 + 해준다. 이를 다 체크하면, (0, 0)에는 출발점에서 도착점까지 갈 수 있는 경우의 수가 남는다. 📌 코드.. 2021. 10. 4. 이전 1 다음 728x90