1-Dimension Dynamic Programming 연습하기

앙박 2025. 3. 16. 22:27

1-Dimension Dynamic Programming 유형의 문제를 풀어볼 거다.

LeetCode 사이트의 "198.House Robber" 를 가져왔다.

내용은 다음과 같다.

1. 일렬로 늘어서 있는 집들을 도둑질 할 거다.
2. 붙어 있는 두 집을 연속해서 도둑질 하면 경찰한테 잡힌다.
3. 집마다 도둑질할 수 있는 돈이 다르다.
4. 경찰한테 안 잡히고 최대한 많은 돈을 얻을 수 있는 방법은?

# 예시
입력: {2, 4, 7, 3} 출력: 9
입력: {9, 3} 출력: 9

자! 여기서 잠깐 멈추고 먼저 문제를 풀어보자. 위에 문제 링크를 달아놨으니 직접 가서 풀어봐도 된다.

사용할 언어도 자유고 풀이 방법도 자유다.

참고로 나는 C++로 DP를 사용해서 풀었다.

#include <iostream>
#include <vector>

static int rob(std::vector<int>& nums) {
    int size = nums.size();

    if (size == 0)
        return 0;
    if (size == 1)
        return nums[0];
    if (size == 2)
        return std::max(nums[0], nums[1]);
    if (size == 3)
        return std::max(nums[0] + nums[2], nums[1]);

    nums[1] = std::max(nums[0]          , nums[1]);
    nums[2] = std::max(nums[0] + nums[2], nums[1]);

    for (auto i = nums.begin() + 3; i < nums.end(); ++i)
        *i = std::max(std::max(*(i - 3), *(i - 2)) + *i, *(i - 1));

    return *(nums.end() - 1);
}

int main()
{
    std::vector<int> i{ 1, 2, 3, 1 };
    std::cout << rob(i);
}

좋아! 깔끔하고 마음에 든다!

static int rob(std::vector<int>& nums) {

메인 로직 함수 정의부다.

변수로 vector<int>를 받는다. (e.g. {2, 4, 1, 8})

& 'reference to' 가 붙어있지만 const는 붙어있지않다. 마음대로 요리해도 된다.

메모리 조금이라도 아끼기 위해 변수로 받은 vector에서 계산하겠다.

int size = nums.size();

    if (size == 0)
        return 0;
    if (size == 1)
        return nums[0];
    if (size == 2)
        return std::max(nums[0], nums[1]);
    if (size == 3)
        return std::max(nums[0] + nums[2], nums[1]);

내 풀이에서 dp는 4번째부터 적용하면 된다.

따라서 4번째 이전의 계산은 if 문에서 따로 계산하고 return으로 반환한다.

    nums[1] = std::max(nums[0] , nums[1]);
    nums[2] = std::max(nums[0] + nums[2] , nums[1]);

    for (auto i = nums.begin() + 3; i < nums.end(); ++i)
        *i = std::max(std::max(*(i - 3), *(i - 2)) + *i, *(i - 1));

    return *(nums.end() - 1);

여기가 dp가 적용되는 부분이다.

집 터는 시뮬레이션을 야무지게 돌리며 차근차근 계산을 쌓아 올린다.

예를 들어, [ 7, 2, 9, 3, 1 ]의 입력이 주어졌다고 해보자.

첫 번째 집을 터는 경우는 한 가지니 두 번째 집부터 생각해보자.

첫 번째 집과 두 번째 집을 연속해서 도둑질하면 경찰한테 잡히니까, 첫 번 째 집과 두 번째 집 중 어디를 털지 결정해야 한다. 보아하니 첫 번째 집을 터는 것이 더 이득이다.

결국 내가 두 번째 집까지 왔을 때 첫 번째 집을 미리 털어놔야 제일 이득이다.

때문에 주어진 입력을 [7, 7, 9, 3, 1]로 바꿔줄 수 있다. 두 번째 집까지 왔을 때 최대 이득이 7이라는 정보를 넣어준 거다.

이 정보를 처음부터 끝까지 계속 축적할 거다.

자 이제 어떻게 축적하는지 생각해보자.

[..., a, b, c, d, f, G]

G라는 집까지 당도했을 때 최대 이득은 어떻게 계산할까?

결론만 말하자면 "(1)이전 집(f)을 털었을 때 최대 이득"과 "(2)지금 집(G)을 털었을 때 최대 이득" 중 큰 값을 넣어주면 된다. 집을 연속해서 두 번 도둑질하면 경찰한테 잡히니까, 두 집 중 하나만 털면 되는 개념이다.

지금 집(G)를 털었을 때 최대 이득은 c와 d 중 최대값에 G의 값을 더해주면 된다. 이렇게 계산하면 a나 b같이 앞에 있는 집들은 이미 c와 d에서 계산을 끝낸 상태기 때문에 고려하지 않는다.