문제 설명
•
자두가 최대 W번 이동하며 T초 동안 떨어지는 자두를 최대로 받을 수 있는 개수를 구하는 문제
예제 입력/출력
•
입력1
7 2
2
1
1
2
2
1
1
Plain Text
복사
•
출력1
6
Plain Text
복사
제약 조건
•
•
문제 풀이
풀이1 브루트 포스 -
풀이2 그리디
•
풀이3 DP -
◦
자두는 최대 W번 움직일 수 있으며, 매 초마다 1번 또는 2번 나무에서 자두가 떨어진다.
◦
따라서, 시간(T)과 움직인 횟수(W)에 따라 최적의 해를 구하는 DP 테이블을 설계할 수 있다.
T / W | 0 | 1 | 2 |
0초 | 0 | 0 | 0 |
1초 | 0 | 1 | 0 |
2초 | 1 | 1 | 2 |
3초 | 2 | 1 | 3 |
4초 | 2 | 3 | 3 |
5초 | 2 | 4 | 3 |
6초 | 3 | 4 | 5 |
7초 | 4 | 4 | 6 |
DP 테이블 정의
DP 관계식
초기값 처리
풀이 코드
# 입력 받기
T, W = map(int, input().split())
drops = [int(input()) for _ in range(T)]
# DP 테이블 초기화
dp = [[0] * (W + 1) for _ in range(T + 1)]
# DP 수행
for t in range(1, T + 1):
for w in range(W + 1):
# 현재 자두가 떨어지는 나무 번호
tree = drops[t - 1]
# 현재 움직인 횟수에 따라 자두를 받을 수 있는지 확인
if w == 0: # 한 번도 이동하지 않은 경우 (1번 나무 아래)
dp[t][w] = dp[t - 1][w] + (1 if tree == 1 else 0)
else: # 이동한 경우 (이전 상태 고려)
dp[t][w] = max(dp[t - 1][w], dp[t - 1][w - 1]) + (1 if (tree == 1 and w % 2 == 0) or (tree == 2 and w % 2 == 1) else 0)
print(max(dp[T]))
Python
복사