-
[Python] 백준 2579 계단 오르기알고리즘/문제풀이 2021. 9. 11. 21:33728x90
1. 문제 링크
https://www.acmicpc.net/problem/2579
2. 문제 요약
계단에 점수가 있을 때 게임에서 얻을 수 있는 점수의 최댓값을 구한다. 단 3개 이상의 연속된 계단은 안됨!
3. 아이디어 정리
- dp[i][j] 정의: 현재까지 j개의 계단을 연속해서 밟고 i번째 계단까지 올라섰을 때 최댓값. i 계단은 밟음
- 점화식 (연속으로 최대 2개만 가능하니 아래 두 점화식이 나온다.)
- dp[i][1] = max(dp[i - 2][1], dp[i - 2][2]) + array[i] # 연속 1개만 밟아야한다(현재 계단만) 따라서 현재 -2 계단 중 최댓값을 더한다.
- dp[i][2] = dp[i - 1][1] + array[i] # 연속 2개를 밟아야 한다. 따라서 이전 계단 밟은 값 중 최댓값을 더한다.
4. 문제 풀이
4-1. 내 풀이
import sys n = int(sys.stdin.readline().split()[0]) array = [0 for _ in range(n + 1)] for i in range(1, n + 1): array[i] = (int(sys.stdin.readline())) if n == 1: print(array[1]) else: # 초기 세팅 d[i][j] - 현재까지 j개의 계단을 연속해서 밟고 i번째 계단까지 올라섰을때 최댓값 d = [[0, 0, 0] for _ in range(n + 1)] d[1][1] = array[1] d[1][2] = 0 d[2][1] = array[2] d[2][2] = array[1] + array[2] for i in range(3, n + 1): # 현재까지 연속으로 1개만 밟은 경우는 현재 i - 2 d에서 값 얻기 d[i][1] = max(d[i - 2][1], d[i - 2][2]) + array[i] # 현재까지 연속으로 2개 밟은 경우는 i -1(이전에) 1개 밟은 최댓값 + 현재 계단 점수 d[i][2] = d[i - 1][1] + array[i] # 전계단 밝고, 현재계단 밟음 print(max(d[n][1], d[n][2]))
5. 결론
- 2차원 dp문제
'알고리즘 > 문제풀이' 카테고리의 다른 글
[Python] Programmers 6주차_복서 정렬하기 (0) 2021.09.18 [Python] 백준 16938 캠프 준비 (0) 2021.09.11 [Python] Programmers 위클리 챌린지 5 모음 사전 (0) 2021.09.11 [Python] Programmers 키패드 누르기 (0) 2021.09.04 [Python] Programmers 직업군 추천하기 (0) 2021.09.04