백준 2579번
- 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
- 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
- 마지막 도착 계단은 반드시 밟아야 한다.
total = int(input())
arr = []
for i in range(total):
arr.append(int(input()))
isChosenArr = [False] * total
rev = list(reversed(arr))
sco = [rev[0], rev[1]]
isChosenArr[0] = True
isChosenArr[1] = True
for i in range(2, total):
if rev[i] >= rev[i-1]:
if isChosenArr[i-1]:
sco[i-1] = rev[i]
isChosenArr[i-1] = False
isChosenArr[i] = True
else:
sco.append(rev[i])
isChosenArr[i] = True
else:
if isChosenArr[i-1] and isChosenArr[i-2]:
continue
else:
sco.append(rev[i])
isChosenArr[i] = True
print(sum(sco))
동적계획법 이론대로 풀어보려고 했다.
그런데 먼가 자꾸 삐꺽거려서 ㅠㅠ 풀이를 찾아보았다
다른 사람들의 풀이와 내 풀이는 사실 비슷했다. </br> 내 풀이는 마지막 계단은 항상 딛고 올라오므로, 마지막 계단 점수를 리스트에 먼저 넣어놓고 거꾸로 딛어 내려가서 점수를 계산하였는데 여기서 한 가지를 더 고려해야하는 듯 했다.
마지막 계단을 딛는데,
- 마지막 전 계단을 딛고 또 딛어서 올라왔는가?
- 마지막 전전 계단을 딛고 마지막 계단을 딛고 올라왔는가?
이 두 가지까지 고려해서 더 높은 점수를 받는 것으로 정답을 내는 코드를 짜야하는 듯 하다.
import sys
input = sys.stdin.readline
n = int(input())
stairs = []
dp = []
for i in range(n):
stairs.append(int(input())) # 계단 점수 리스트 만들기
if n==1: # 계단이 1개일 때
print(stairs[0])
exit()
elif n == 2: # 계단이 2개알 때
print(max(stairs[0]+stairs[1], stairs[1]))
exit()
dp.append(stairs[0]) # 첫 번째 계단 점수 추가
dp.append(max(dp[0]+stairs[1], stairs[1])) # 두 번째 계단 점수와 첫 번째 계단 점수 합하여 비교 후 더 큰 값으로 추가
dp.append(max(dp[0]+stairs[2], stairs[1]+stairs[2])) # 첫 번째 계단 점수와 세 번째 계단 점수 합한 값 vs 두 번째 계단 점수와 세 번째 계단 점수 합한 값 비교 후 더 큰 값으로 추가
for i in range(3, n): # 네 번째 계단부터는 for문 돌기
dp.append(max(dp[i-2]+stairs[i], dp[i-3]+stairs[i-1]+stairs[i]))
# 두 번째 계단과 네 번째 계단을 합한 값 vs 첫 번째 계단과 세 번째 계단, 네 번째 계단 합한 값 비교 후 더 큰 값으로 추가 -> 이후 동일
print(dp[-1]) # dp리스트의 제일 마지막 값 프린트(총 합이므로)
위 코드는 내가 참고한 사이트 중에 제일 이해가 잘 되었던 사이트에서 가져온 코드이다! </br>
DP의 제일 중요한 포인트는 처음부터 반복이 될 부분까지 내가 직접 손으로 풀어보는 것이다. </br>
그것으로 규칙을 정하고 동적계획법 방식인 Top-down이나, Bottom-up으로 더 효율적인 방법을 택해서 코드를 짜나가면 될 것이다.