배열 문제를 풀다 보면
현재 값을 선택할지, 아니면 건너뛸지를 결정해야 하는 경우가 자주 나옵니다.

이번 글에서는
서로 붙어 있는 위치를 동시에 선택할 수 없을 때 최대 합을 구하는 유형을 정리해보겠습니다.

처음 보면 경우의 수가 많아 보여 복잡해 보이지만,
이전 결과를 잘 활용하면 한 번의 순회로 해결할 수 있습니다.

문제

게임 맵에 여러 개의 보상 구역이 일렬로 배치되어 있습니다.
각 구역에는 획득 가능한 보상 점수가 적혀 있습니다.

단, 서로 바로 붙어 있는 두 구역은 경보 시스템 때문에 같은 턴에 함께 선택할 수 없습니다.

이 규칙을 지키면서 얻을 수 있는 최대 보상 점수를 구하는 함수를 작성해보세요.

예시 1

입력: [3, 7, 4, 6, 5]
출력: 13

설명:

  • 7과 6을 선택하면 13
  • 서로 붙어 있지 않으므로 선택 가능
  • 다른 조합보다 더 큰 값

예시 2

입력: [8, 2, 9, 3, 1]
출력: 18

설명:

  • 8, 9, 1을 선택하면 18
  • 인접한 구역을 동시에 선택하지 않았으므로 가능

조건

  • 점수는 0 또는 음수일 수도 있습니다.
  • 아무 구역도 선택하지 않는 것도 가능합니다.

어떻게 생각해야 할까

어떤 위치에 도착했을 때 선택지는 두 가지입니다.

  1. 현재 구역을 선택하지 않는다

    • 바로 이전까지의 최대 점수를 그대로 사용

  2. 현재 구역을 선택한다

    • 바로 앞 구역은 선택할 수 없으므로, 전전 위치까지의 최대 점수 + 현재 점수

즉, 현재 위치의 최대값은 아래 둘 중 큰 값입니다.

현재 최대 = max(이전 최대, 전전 최대 + 현재 값)

DP 아이디어

이 문제는 DP(동적 계획법)의 대표적인 유형입니다.

배열을 왼쪽부터 보면서 각 위치까지 만들 수 있는 최대 점수를 저장해 나가면 됩니다.

예를 들어 [3, 7, 4, 6, 5]를 보면:

  • 3까지의 최대는 3
  • 7까지의 최대는 7
  • 4까지의 최대는 7
  • 6까지의 최대는 13
  • 5까지의 최대는 13

이렇게 누적해서 답을 구할 수 있습니다.

점화식

dp[i]를 i번째 구역까지 고려했을 때 얻을 수 있는 최대 점수라고 하면:

dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])

뜻은 다음과 같습니다.

  • dp[i - 1] : 현재 구역을 선택하지 않는 경우
  • dp[i - 2] + nums[i] : 현재 구역을 선택하는 경우

파이썬 풀이 1 — 이해하기 쉬운 방식

def max_reward(nums):
    if not nums:
        return 0

    if len(nums) == 1:
        return max(0, nums[0])

    dp = [0] * len(nums)
    dp[0] = max(0, nums[0])
    dp[1] = max(dp[0], nums[1])

    for i in range(2, len(nums)):
        dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])

    return dp[-1]

파이썬 풀이 2 — 공간 최적화

이 문제는 매번 필요한 값이 두 개뿐입니다.

  • 이전 최대값
  • 전전 최대값

그래서 배열 전체를 저장하지 않고도 해결할 수 있습니다.

def max_reward(nums):
    prev_two = 0
    prev_one = 0

    for num in nums:
        current = max(prev_one, prev_two + num)
        prev_two = prev_one
        prev_one = current

    return prev_one

예제로 따라가 보기

입력:

[3, 7, 4, 6, 5]

초기값:

prev_two = 0
prev_one = 0

3을 볼 때

current = max(0, 0 + 3) = 3

7을 볼 때

current = max(3, 0 + 7) = 7

4를 볼 때

current = max(7, 3 + 4) = 7

6을 볼 때

current = max(7, 7 + 6) = 13

5를 볼 때

current = max(13, 7 + 5) = 13

최종 정답은 13입니다.

이 문제가 다른 DP와 다른 점

이 문제는 경우의 수를 세는 DP와 달리, 각 위치에서 더 큰 값을 남기는 선택형 DP라는 점이 중요합니다.

예를 들어 이동 방법 수를 세는 문제라면 이전 상태들을 더해 나가면 되지만, 이 문제는 더한다고 끝나지 않고 선택할지 말지를 비교해서 최댓값을 남겨야 합니다.

즉, 같은 DP라도 이 글은 “몇 가지 방법이 있는가”보다 “지금까지 얻을 수 있는 최선의 값이 무엇인가”에 더 가깝습니다.

실수하기 쉬운 부분

1. 현재 값을 고르면 바로 이전 값은 못 고릅니다

이 문제의 핵심 제약은 인접한 두 구역을 함께 선택할 수 없다는 점입니다. 그래서 현재 값을 고르는 경우는 항상 i - 2와 연결해서 봐야 합니다.

2. greedy처럼 보이지만 greedy로는 충분하지 않습니다

눈앞의 큰 값만 고르면 될 것처럼 보여도, 앞뒤 조합에 따라 전체 합이 달라질 수 있습니다. 그래서 이 문제는 매 순간 최댓값을 남기는 DP 흐름으로 보는 것이 안전합니다.

3. 음수가 있을 때는 초기값을 조심해야 합니다

이 글의 풀이에서는 아무것도 선택하지 않는 것도 가능하다고 두었기 때문에, 초기값을 max(0, nums[0])처럼 잡고 시작합니다. 문제 조건이 달라지면 이 초기 처리도 달라질 수 있습니다.

시간 복잡도

DP 배열 사용

  • 시간 복잡도: O(N)
  • 공간 복잡도: O(N)

변수 2개만 사용

  • 시간 복잡도: O(N)
  • 공간 복잡도: O(1)

정리

이 문제의 핵심은 간단합니다.

  • 현재 값을 고르지 않으면 이전 최대값 유지
  • 현재 값을 고르면 전전 최대값에 현재 값을 더함

즉, 매 순간 지금 선택할지, 건너뛸지만 판단하면 됩니다.

이 구조를 익혀 두면 비슷한 DP 문제를 만났을 때도 훨씬 덜 헷갈립니다.