https://www.acmicpc.net/problem/2579
시간 1초, 메모리 128MB
input :
- N (1 <= N <= 300)
- S (1 <= S <= 10,000)
output :
- 점수의 최댓값을 출력.
조건 :
- 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
- 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
- 마지막 도착 계단은 반드시 밟아야 한다.
i - 1번째에서 i번으로 갈 때 고려해야 할 사항은. 1. 연속적인가? 2. 연속적이지 않는가 이다.
2개의 변수를 이용해서 1. 2. 일 때를 구분 해주고.
그림에서는 y 자리가 0 일 때는 한 계단을 오르는 것. 자리가 1일 때는 두 계단을 오르는 것이다.
실패.
계단은 2개를 밟을 수 있는데 하나만 따져서 문제인가 싶어서.
0번(아직 2개를 밟을 수 있음)
1번(아직 1개를 밟을 수 있음)
2번(못 밟음)
으로 나눠서 했는데 틀렸다.
사람들 풀이를 보니 탑 다운 으로 풀었는데 맨 처음 접근하던게 그나마 맞긴 했다.
마지막 계단에 도착하는 경우.
1. 바로 직전 계단에서 올라옴.
2. 2계단 밑에서 올라옴.
이것인데.
- 바로 직전에서 올라오려면. 이미 1칸을 밟고 있어야 한다. 즉, i - 1번째 계단 값도 생각을 해야 하고. 그 전의 dp 값을 더 해 주어야 한다.
i - 1 번째 계단을 올라올 때는 무조건 2계단 밑에서 올라오기 때문에 dp[(i - 1) - 2] 도 더해준다. - 2계단 밑에서 올라오는 경우는 그냥 dp[i - 2]를 더해주자.
import sys
N = int(sys.stdin.readline())
data = [0 for i in range(301)]
dp = [0 for i in range(301)]
for i in range(N):
S = int(sys.stdin.readline())
data[i] = S
dp[0] = data[0]
dp[1] = data[1] + data[0]
dp[2] = max(data[1] + data[2], data[0] + data[2])
for i in range(3, N):
dp[i] = max(data[i] + data[i - 1] + dp[i - 3], data[i] + dp[i - 2])
print(dp[N - 1])
