[백준 2240] 자두나무 Python 풀이

[백준 2240] 자두나무 Python 풀이

📌 문제 분석

• N(시간) 동안 1번 또는 2번 나무에서 자두가 떨어진다.
• 자두를 최대한 많이 먹는 것이 목표이다.
• 최대 W번 이동이 가능하며, 이를 고려해 최적의 이동 전략을 세워야 한다.

🚨 시행착오

초기 접근 방식

• 단순히 1번 나무에서 계속 기다리거나 번갈아 가며 이동하는 방법을 생각했다.
• 그러나 이동 횟수 제한이 있어 무작정 이동하는 것은 비효율적이었다.

문제점

• Brute-force 방식으로 접근하면 경우의 수가 너무 많아진다.
• DP로 접근해야 한다는 생각은 들었지만, 상태를 어떻게 정의할지가 어려웠다.

해결 과정

• DP 테이블을 정의하고, 시간을 기준으로 자두를 먹을 수 있는 최대 개수를 갱신하는 방식으로 접근했다.
• 이동 횟수에 따라 자두를 먹을 수 있는 최대 개수를 관리하는 방식으로 최적화했다.

💡 해결 방안

import sys

sys.stdin = open("input.txt", "r")

T, W = map(int, input().split())
dp = [[0] * (T+1) for _ in range(W+1)]
inp = [int(input()) for _ in range(T)]

# 이동 없이 1번 나무에서 자두를 먹는 경우
for j in range(1, T+1):
    dp[0][j] = dp[0][j-1] + (inp[j-1] == 1)

for i in range(1, W+1):
    for j in range(1, T+1):
        current_tree = 2 if i % 2 else 1
        dp[i][j] = max(dp[i][j-1] + (inp[j-1] == current_tree), dp[i-1][j-1] + (inp[j-1] == current_tree))

print(max(dp[i][T] for i in range(W+1)))

🎯 문제 해결의 핵심 포인트

1. DP를 활용해 특정 시간과 이동 횟수에 따른 최적의 자두 개수를 저장.
2. 이동을 할 때와 하지 않을 때를 나누어 최댓값을 갱신.
3. 이동 횟수가 홀수일 때는 2번 나무, 짝수일 때는 1번 나무에서 자두를 먹을 수 있도록 설정.

📝 예제로 이해하기

입력:
5 2
2
1
1
2
2

출력:
4

예제 설명

• 2초에 2번 나무 → 1번으로 이동 (자두 1개)
• 3초에 1번 나무 (자두 1개 추가)
• 4초에 1번 나무 (자두 1개 추가)
• 5초에 2번 나무로 이동 (자두 1개 추가)

✨ 이 문제를 통해 배운 점

1. DP 문제에서 상태를 정의하는 것이 중요하다.
2. 이동 횟수 제한이 있을 때 DP를 활용하면 효율적으로 해결할 수 있다.
3. 단순한 Brute-force 접근법이 아닌 최적화된 방법을 고민하는 습관이 필요하다.

🔍 코드 설명

• dp[i][j]는 j초까지 i번 이동했을 때 얻을 수 있는 최대 자두 개수를 의미한다.
• 이전 상태를 참고해 이동했을 때와 하지 않았을 때 중 최댓값을 선택한다.
• 최종적으로 가능한 모든 이동 횟수에서 최댓값을 찾아 정답을 도출한다.