알고리즘 문제 해결 전략 및 동적 계획법 심화

나무 심기 문제

문제 설명

일직선 위에 서로 다른 위치에 n 그루의 나무가 심어져 있습니다. 각 나무의 위치는 정수 ai로 주어집니다.

기존 나무의 위치를 변경할 수 없지만, 새로운 나무를 추가로 심어 모든 나무(기존 나무와 새로 심은 나무 모두 포함)의 위치를 정렬했을 때, 인접한 나무들 사이의 간격이 모두 동일하도록 만들고 싶습니다. 새로 심는 나무의 위치도 정수여야 합니다.

이때, 최소한으로 더 심어야 하는 나무의 수를 계산하여 출력하세요.

문제 해결 전략

주어진 나무들은 이미 오름차순으로 정렬되어 있다고 가정합니다. 모든 나무의 간격을 동일하게 만들려면, 새로 심은 나무를 포함한 모든 인접한 나무 사이의 간격이 어떤 공통된 값 D의 배수가 되어야 합니다. 가장 작은 D를 찾기 위해서는 기존 나무들 사이의 모든 간격의 최대공약수(GCD)를 구해야 합니다.

  1. 인접 간격 계산: 먼저, 입력받은 나무들의 위치 배열을 순회하며 인접한 두 나무 사이의 거리 차이를 계산합니다. 예를 들어, 나무 위치가 [2, 6, 12, 15]라면, 간격은 4 (6-2), 6 (12-6), 3 (15-12)이 됩니다.
  2. GCD 초기화: 첫 번째 계산된 간격을 현재 GCD의 초기값으로 설정합니다.
  3. GCD 반복 계산: 유클리드 호제법을 사용하여 현재 GCD 값과 나머지 간격들의 GCD를 순차적으로 계산합니다. 예를 들어:
    • gcd(4, 6)을 계산하여 2를 얻습니다.
    • 다시 gcd(2, 3)을 계산하여 1을 얻습니다.
  4. 최종 결과 도출: 모든 간격에 대한 GCD 계산이 완료되면, 최종 GCD 값이 모든 나무가 가질 수 있는 최소 공통 간격이 됩니다. 위의 예시에서는 1이 됩니다.

이제 최소 공통 간격 k를 알았으니, 가장 왼쪽 나무부터 가장 오른쪽 나무까지의 총 거리를 k로 나누면, 이 총 거리에 k 간격으로 몇 개의 구간이 생기는지 알 수 있습니다. 즉, (가장 오른쪽 나무 위치 - 가장 왼쪽 나무 위치) / k가 구간의 개수입니다. 총 나무의 수는 이 구간 개수에 1을 더한 값과 같습니다. 마지막으로, 이 값에서 기존 나무의 개수 n을 빼면 새로 심어야 할 최소 나무의 수가 됩니다.

구현 코드

#include <iostream>
#include <vector>
#include <numeric> // for std::gcd
#include <algorithm> // for std::sort

long long calculate_gcd(long long a, long long b) {
    return std::gcd(a, b);
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int num_trees;
    std::cin >> num_trees;

    std::vector<long long> tree_positions(num_trees);
    for (int i = 0; i < num_trees; ++i) {
        std::cin >> tree_positions[i];
    }

    std::sort(tree_positions.begin(), tree_positions.end());

    if (num_trees <= 1) {
        std::cout << 0 << std::endl;
        return 0;
    }

    std::vector<long long> differences;
    for (int i = 1; i < num_trees; ++i) {
        differences.push_back(tree_positions[i] - tree_positions[i-1]);
    }

    long long common_divisor = differences[0];
    for (size_t i = 1; i < differences.size(); ++i) {
        common_divisor = calculate_gcd(common_divisor, differences[i]);
    }

    long long total_span = tree_positions[num_trees - 1] - tree_positions[0];
    long long required_trees = (total_span / common_divisor) + 1;

    std::cout << required_trees - num_trees << std::endl;

    return 0;
}

식인 국가 문제

문제 설명

식인 국가의 왕은 사람을 잡아먹는 것을 좋아합니다. 현재 n명의 사람이 왼쪽부터 오른쪽으로 1번부터 n번까지 번호가 매겨져 한 줄로 서 있습니다.

왕은 숫자 k (단, k ≥ 2)를 특히 좋아합니다. 그는 다음과 같은 "번호를 세고 사람을 잡아먹는" 과정을 반복합니다:

  • 현재 살아있는 사람들은 원래의 상대적인 순서를 유지한 채 왼쪽부터 차례로 1, 2, 3, ... 하고 번호를 다시 세기 시작합니다.
  • 이번 차례에, k의 배수가 아닌 번호를 외친 사람들은 순서대로 잡아먹힙니다.
  • 이번 차례가 끝나면, 남은 사람들은 다시 1부터 번호를 세며 다음 차례로 넘어갑니다.

주어진 n과 k 값에 관계없이, 왕은 결국 모든 사람을 잡아먹을 수 있습니다.

여러분도 이 n명 중 한 명입니다. 여러분은 가장 마지막에 잡아먹힌 사람의 처음 번호가 몇 번인지 알고 싶습니다.

문제 해결 전략

이 문제는 순수한 수학적 사고를 요구합니다. 매 라운드마다 k의 배수가 아닌 사람들이 제거되므로, 살아남는 사람들은 상대적인 순서에서 k의 배수에 해당하는 번호를 외친 사람들입니다. 이 과정은 결국 가장 마지막까지 살아남는 사람이 원래 번호에서 어떤 특정한 패턴을 가짐을 의미합니다.

결론적으로, 마지막까지 살아남는 사람의 원래 번호는 n 이하의 숫자 중 가장 큰 k의 거듭제곱으로 나누어떨어지는 수, 즉 kx의 배수 형태가 됩니다. 더 정확히는, n을 넘지 않는 가장 큰 k의 거듭제곱 kx를 찾고, 그 kx의 배수 중 n 이하이면서 가장 큰 수가 됩니다. 이는 n을 kx로 나눈 몫에 다시 kx를 곱하는 것과 같습니다.

구현 코드

#include <iostream>

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    long long total_people, divisor_k;
    std::cin >> total_people >> divisor_k;

    long long largest_power_of_k = 1;
    // total_people 이하인 k의 가장 큰 거듭제곱을 찾는다.
    // 여기서 largest_power_of_k는 k의 거듭제곱(k^x)이 된다.
    while (largest_power_of_k * divisor_k <= total_people) {
        largest_power_of_k *= divisor_k;
    }

    // 마지막에 남는 사람의 원래 번호는 total_people 이하의 수 중 
    // largest_power_of_k의 가장 큰 배수이다.
    long long last_person_id = (total_people / largest_power_of_k) * largest_power_of_k;

    std::cout << last_person_id << std::endl;

    return 0;
}

동적 계획법 (Dynamic Programming) 소개

동적 계획법(DP)은 중복되는 부분 문제와 최적 부분 구조의 특성을 가진 문제들을 해결하기 위한 알고리즘 설계 기법입니다. 이 방법은 복잡한 문제를 더 작은 하위 문제들로 분해하고, 하위 문제의 해결 결과를 저장하여 중복 계산을 피함으로써 효율성을 높입니다.

핵심 개념

  • 최적 부분 구조 (Optimal Substructure): 전체 문제의 최적 해가 그 부분 문제의 최적 해를 포함하는 경우를 말합니다.
  • 중복 부분 문제 (Overlapping Subproblems): 동일한 하위 문제가 문제 해결 과정에서 여러 번 반복해서 계산되는 경우를 의미합니다. DP는 이러한 중복 계산을 메모이제이션(기억화)을 통해 피합니다.

동적 계획법의 두 가지 구현 방식

  1. 하향식 (Top-Down, 메모이제이션 재귀)
    • 원래 문제에서 시작하여 재귀적으로 하위 문제들을 분해합니다.
    • 이미 계산된 하위 문제의 결과는 캐시(배열 또는 해시 테이블 등)에 저장하여, 필요할 때 재사용합니다.
    • 문제 분해가 직관적이지만, 재귀 호출 스택 오버헤드가 발생할 수 있습니다.
  2. 상향식 (Bottom-Up, 반복문 채우기)
    • 가장 작은 하위 문제부터 시작하여 점진적으로 전체 문제의 해를 구축합니다.
    • 보통 배열(DP 테이블)을 사용하여 순서대로 결과를 채워나갑니다.
    • 공간 효율성이 더 좋고 재귀 스택 오버헤드가 없습니다.

동적 계획법 적용 단계

  1. 문제 분석
    • 문제의 상태 정의(예: dp[i]가 무엇을 의미하는지)를 명확히 합니다.
    • 상태 전이식(예: dp[i-1]에서 dp[i]를 어떻게 유도하는지)을 수립합니다.
    • 초기 조건(예: dp[0]의 값)을 설정합니다.
  2. 상태 전이식 수립
    • 문제의 논리에 따라 수학적 관계를 정립합니다. 예를 들어, 피보나치 수열은 다음과 같습니다:
    • dp[i] = dp[i-1] + dp[i-2]
  3. 경계 조건 설정
    • 기본적인 경우를 초기화합니다. 예를 들어, dp[0] = 0, dp[1] = 1.
  4. 공간 복잡도 최적화
    • 일부 문제에서는 DP 테이블의 크기를 줄일 수 있습니다. 예를 들어, 피보나치 수열은 이전 두 상태만 저장하면 됩니다:
    # Python 예시
prev_val, current_val = 0, 1
for _ in range(2, n + 1):
    prev_val, current_val = current_val, prev_val + current_val

대표적인 문제 예시

  1. 피보나치 수열
    • 상태 정의: dp[i]는 i번째 피보나치 수입니다.
    • 상태 전이식: dp[i] = dp[i-1] + dp[i-2].
  2. 배낭 문제 (Knapsack Problem)
    • 상태 정의: dp[i][j]는 i번째 아이템까지 고려했을 때, j 용량에서 얻을 수 있는 최대 가치입니다.
    • 상태 전이식: dp[i][j] = \max(dp[i-1][j], dp[i-1][j-w_i] + v_i)

일반적인 최적화 기법

  • 스크롤링 배열 (Rolling Array): 2차원 DP 테이블을 1차원으로 압축하여 공간 복잡도를 줄입니다.
  • 상태 압축 (State Compression): 비트 연산 등을 활용하여 상태를 간결하게 표현합니다 (예: 외판원 문제).

위의 프레임워크를 이해하고 대표적인 문제들을 연습함으로써 동적 계획법의 핵심 사상과 적용 방법을 익힐 수 있습니다.

보스 몬스터 공격 문제

문제 설명

여러분은 레벨업 게임을 즐기고 있습니다. 현재 강력한 보스 몬스터와 전투 중입니다.

전투는 총 n초 동안 진행됩니다. 매 초마다 여러분은 두 가지 선택지 중 하나를 고를 수 있습니다:

  • 일반 공격: k만큼의 피해를 입힙니다.
  • 스킬 사용: ai만큼의 피해를 입힙니다.

몇 가지 규칙이 있습니다:

  • 만약 i-1초에 스킬을 사용했다면, i초에 다시 스킬을 사용할 경우 피해량이 두 배가 되어 2 × ai만큼의 피해를 입힙니다.
  • 연속해서 3초 이상 스킬을 사용할 수 없습니다. 즉, 3초 연속으로 스킬만 사용하는 상황은 허용되지 않습니다.

총 n초 동안 몬스터에게 최대로 가할 수 있는 피해량을 계산하여 출력하세요.

문제 해결 전략

이 문제는 공격 전략 최적화를 위한 동적 계획법 문제입니다. 다음과 같이 상태를 정의하고 전이식을 수립할 수 있습니다.

상태 정의

  • dp[i][0]: i번째 공격에서 일반 공격(k 피해)을 선택했을 때, 이전 i번의 공격으로 얻을 수 있는 최대 총 피해량.
  • dp[i][1]: i번째 공격에서 일반 스킬(a[i] 피해)을 선택했을 때, 이전 i번의 공격으로 얻을 수 있는 최대 총 피해량.
  • dp[i][2]: i번째 공격에서 강화 스킬(2 × a[i] 피해)을 선택했을 때, 이전 i번의 공격으로 얻을 수 있는 최대 총 피해량.

상태 전이식

  • dp[i][0] (일반 공격):

    현재 i번째에 일반 공격을 했다면, i-1번째에는 어떤 공격이든 가능합니다. 따라서 이전 세 가지 상태 중 가장 큰 값에 일반 공격 피해량 k를 더합니다.

    dp[i][0] = max({dp[i-1][0], dp[i-1][1], dp[i-1][2]}) + k;
  • dp[i][1] (일반 스킬):

    현재 i번째에 일반 스킬을 사용했다면, 연속 3회 스킬 사용 금지 규칙 때문에 i-1번째에는 일반 공격만 가능합니다 (스킬-강화스킬-스킬 패턴을 막기 위해).* 따라서 i-1번째 일반 공격 상태에 현재 일반 스킬 피해량 a[i]를 더합니다.

    dp[i][1] = dp[i-1][0] + a[i];

    *원문 설명과 약간 다르게 해석했지만, 주어진 코드와 "연속 3초 이상 스킬 사용 금지" 조건을 엄격하게 만족시키려면, 일반 스킬은 일반 공격 다음에만 올 수 있고, 강화 스킬은 일반 스킬 다음에만 올 수 있습니다. 이는 "스킬 -> 스킬 -> 스킬" (1->1->1) 또는 "스킬 -> 강화스킬 -> 강화스킬" (1->2->2) 같은 상황을 방지합니다. 원문의 dp[i][1] = dp[i-1][0] + a[i]는 이를 만족시킵니다. 왜냐하면 dp[i-1][1](이전 일반 스킬) 다음에 dp[i][1](현재 일반 스킬)이 올 수 없기 때문입니다. 그리고 dp[i-1][2](이전 강화 스킬) 다음에도 dp[i][1]은 올 수 없습니다. 따라서 dp[i-1][0]에서만 dp[i][1]로 전이되는 것이 맞습니다.

  • dp[i][2] (강화 스킬):

    현재 i번째에 강화 스킬을 사용했다면, 이는 i-1번째에 일반 스킬을 사용했을 때만 가능합니다. 따라서 i-1번째 일반 스킬 상태에 현재 강화 스킬 피해량 2 × a[i]를 더합니다.

    dp[i][2] = dp[i-1][1] + 2 * a[i];

초기 조건

  • dp[0][0] = 0, dp[0][1] = -무한대, dp[0][2] = -무한대 (혹은 dp[1]부터 시작하는 경우, dp[1][0] = k, dp[1][1] = a[1], dp[1][2] = -무한대)
  • -무한대 값은 해당 상태로 도달할 수 없음을 나타냅니다. C++에서는 보통 -0x3f3f3f3f 같은 작은 값을 사용합니다.

최종 결과

n번의 공격 후, 세 가지 최종 상태 중 가장 큰 값을 선택합니다: max({dp[n][0], dp[n][1], dp[n][2]})

구현 코드

#include <iostream>
#include <vector>
#include <algorithm> // for std::max

// DP 테이블: dp_table[i][state]
// state 0: 일반 공격 (Normal Attack)
// state 1: 일반 스킬 (Basic Skill)
// state 2: 강화 스킬 (Enhanced Skill)
long long dp_table[1000005][3];
long long skill_damage_values[1000005]; // 각 초마다 스킬 기본 피해량

const long long INF = 0x3f3f3f3f3f3f3f3fLL; // 충분히 작은 음의 무한대 값

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int total_seconds;
    long long normal_attack_damage;
    std::cin >> total_seconds >> normal_attack_damage;

    for (int i = 1; i <= total_seconds; ++i) {
        std::cin >> skill_damage_values[i];
    }

    // 1초일 때의 초기 상태 설정
    dp_table[1][0] = normal_attack_damage; // 1초에 일반 공격
    dp_table[1][1] = skill_damage_values[1]; // 1초에 일반 스킬
    dp_table[1][2] = -INF; // 1초에는 강화 스킬을 사용할 수 없음 (이전 스킬 필요)

    // 2초부터 total_seconds까지 DP 테이블 채우기
    for (int i = 2; i <= total_seconds; ++i) {
        // i초에 일반 공격: 이전 어떤 상태에서든 가능
        dp_table[i][0] = std::max({dp_table[i-1][0], dp_table[i-1][1], dp_table[i-1][2]}) + normal_attack_damage;
        
        // i초에 일반 스킬: 이전 i-1초에는 일반 공격만 가능 (연속 스킬 방지)
        dp_table[i][1] = dp_table[i-1][0] + skill_damage_values[i];
        
        // i초에 강화 스킬: 이전 i-1초에는 일반 스킬이 사용되었어야 함
        dp_table[i][2] = dp_table[i-1][1] + 2 * skill_damage_values[i];
    }

    // N초까지의 최대 피해량은 세 가지 최종 상태 중 가장 큰 값
    long long max_total_damage = std::max({dp_table[total_seconds][0], dp_table[total_seconds][1], dp_table[total_seconds][2]});
    std::cout << max_total_damage << std::endl;
    
	return 0;
}

2차원 동적 계획법

2차원 동적 계획법(2D DP)은 두 개의 변수나 차원을 포함하는 복잡한 문제를 해결하는 데 효과적인 방법입니다. C++에서는 주로 2차원 배열이나 vector<vector<int>>를 사용하여 구현합니다.

기본 개념

2차원 DP의 핵심은 문제를 더 작은 하위 문제로 나누고, 이 하위 문제들의 해를 2차원 테이블에 저장하는 것입니다. 이 방식은 주로 행렬 경로 찾기 문제, 문자열 매칭 문제 등에 활용됩니다. 핵심은 한 상태에서 다음 상태로의 전이를 정의하는 상태 전이식을 설정하는 것입니다.

구현 단계

  1. DP 배열 정의:

    중간 결과를 저장하기 위해 보통 std::vector<std::vector<int>> 또는 int dp[m][n] 형태의 2차원 배열을 사용합니다. 배열의 크기는 문제 요구사항에 따라 결정됩니다.

  2. 경계 조건 초기화:

    문제의 기본 조건에 따라 DP 배열의 첫 번째 행과 첫 번째 열을 초기화합니다. 이 값들은 문제의 가장 기본적인 경우를 나타냅니다.

  3. DP 배열 채우기:

    중첩 반복문을 사용하여 배열의 각 요소를 순회하고, 상태 전이식에 따라 각 위치의 값을 갱신합니다. 상태 전이식은 현재 상태와 이전 상태들 간의 관계를 정의합니다.

  4. 결과 반환:

    최종 결과는 일반적으로 DP 배열의 특정 위치(예: 오른쪽 하단 또는 특정 좌표)에 저장됩니다.

예시 코드: 행렬 최소 경로 합

다음은 행렬의 왼쪽 상단에서 오른쪽 하단으로 가는 최소 경로 합을 계산하는 대표적인 2차원 DP 문제 예시입니다.

#include <vector>
#include <algorithm> // for std::min

int calculateMinPathSum(std::vector<std::vector<int>>& grid) {
    if (grid.empty() || grid[0].empty()) return 0;

    int num_rows = grid.size();
    int num_cols = grid[0].size();

    // dp_table[r][c]는 (0,0)에서 (r,c)까지의 최소 경로 합을 저장
    std::vector<std::vector<int>> dp_table(num_rows, std::vector<int>(num_cols, 0));
    
    // 시작점 초기화
    dp_table[0][0] = grid[0][0];

    // 첫 번째 열 초기화 (아래로만 이동)
    for (int r = 1; r < num_rows; ++r) {
        dp_table[r][0] = dp_table[r-1][0] + grid[r][0];
    }
    // 첫 번째 행 초기화 (오른쪽으로만 이동)
    for (int c = 1; c < num_cols; ++c) {
        dp_table[0][c] = dp_table[0][c-1] + grid[0][c];
    }
    
    // 나머지 DP 테이블 채우기
    for (int r = 1; r < num_rows; ++r) {
        for (int c = 1; c < num_cols; ++c) {
            // 위에서 오거나 왼쪽에서 오는 경로 중 최소값을 선택
            dp_table[r][c] = std::min(dp_table[r-1][c], dp_table[r][c-1]) + grid[r][c];
        }
    }
    
    return dp_table[num_rows-1][num_cols-1];
}

공간 복잡도 최적화

어떤 경우에는 2차원 DP를 1차원 DP로 최적화하여 공간 복잡도를 줄일 수 있습니다. 예를 들어, 현재 행의 값이 이전 행이나 이전 열의 값에만 의존하는 경우, 한 행 또는 한 열의 데이터만 유지하면 됩니다.

#include <vector>
#include <algorithm> // for std::min

int calculateMinPathSumOptimized(std::vector<std::vector<int>>& grid) {
    if (grid.empty() || grid[0].empty()) return 0;

    int num_rows = grid.size();
    int num_cols = grid[0].size();
    
    // dp_row[c]는 현재 행의 (0, c)까지의 최소 경로 합을 저장
    std::vector<int> dp_row(num_cols, 0);
    
    // 첫 번째 행 초기화
    dp_row[0] = grid[0][0];
    for (int c = 1; c < num_cols; ++c) {
        dp_row[c] = dp_row[c-1] + grid[0][c];
    }
    
    // 나머지 행들을 순회하며 DP 업데이트
    for (int r = 1; r < num_rows; ++r) {
        // 현재 행의 첫 번째 열 업데이트 (위에서만 올 수 있음)
        dp_row[0] += grid[r][0];
        for (int c = 1; c < num_cols; ++c) {
            // 위에서 오거나 왼쪽에서 오는 경로 중 최소값을 선택
            // dp_row[c]는 이전 행의 dp_row[c] (위에서 오는 값)
            // dp_row[c-1]는 현재 행의 dp_row[c-1] (왼쪽에서 오는 값)
            dp_row[c] = std::min(dp_row[c], dp_row[c-1]) + grid[r][c];
        }
    }
    
    return dp_row[num_cols-1];
}

일반적인 적용 시나리오

2차원 DP는 다양한 문제에 광범위하게 적용됩니다:

  • 행렬 내 최장 증가 경로
  • 편집 거리(Levenshtein 거리) 계산
  • 배낭 문제의 다양한 변형
  • 문자열 매칭 문제 (예: 정규 표현식 매칭)

주의사항

  • 정확성 검증: 상태 전이식이 올바른지 소규모 예시로 수동 계산하여 검증합니다.
  • 경계 조건 처리: 배열 인덱스 범위를 벗어나지 않도록 경계 조건을 세심하게 다룹니다.
  • 공간 복잡도: 메모리 제약이 있는 경우 공간 최적화 가능성을 고려합니다.
  • 시간 복잡도 분석: 2차원 DP는 일반적으로 O(mn)의 시간 복잡도를 가집니다.

미궁 탈출 문제

문제 설명

n × m 크기의 격자형 미궁이 주어집니다. i행 j열의 칸에는 정수 ai,j가 표시되어 있으며, 이 칸으로 진입하면 해당 값만큼의 피해를 입습니다.

여러분은 왼쪽 상단 (1,1)에서 출발하여 오른쪽 하단 (n,m)까지 이동해야 합니다. 각 단계에서는 오른쪽 또는 아래쪽으로만 이동할 수 있습니다.

한 경로의 총 피해량은 경로를 따라 지나온 모든 칸의 피해량 합(출발지와 도착지 포함)으로 정의됩니다.

가능한 경로의 총 피해량이 매우 많을 수 있으므로, 여러분은 총 피해량을 10007로 나눈 나머지 값에만 관심이 있습니다. 모든 경로에 대해 "총 피해량 mod 10007"이 가질 수 있는 서로 다른 값의 개수를 계산하여 출력하세요.

문제 해결 전략

이 문제 또한 동적 계획법으로 해결할 수 있습니다. 경로는 오직 오른쪽이나 아래로만 이동하므로, 각 칸 (i,j)에 도달했을 때 가능한 피해량의 나머지를 추적해야 합니다. 피해량의 나머지가 0부터 10006까지의 값 중 무엇이 가능한지를 불리언 배열로 기록합니다.

상태 정의

dp[r][c][k]: 위치 (r,c)에 도달했을 때, 총 피해량의 나머지가 k가 되는 경로가 존재하면 true, 아니면 false.

상태 전이식

위치 (r,c)에 도달하여 k만큼의 나머지 피해량을 얻을 수 있다면, 다음 두 가지 경로로 이동할 수 있습니다:

  • 아래로 이동: (r+1, c)로 이동합니다. 이때, 새로운 피해량 나머지는 (k + a[r][c]) % 10007이 됩니다. 
    dp[r+1][c][(k + damage_map[r][c]) % MOD] = true;
  • 오른쪽으로 이동: (r, c+1)로 이동합니다. 이때, 새로운 피해량 나머지는 (k + a[r][c]) % 10007이 됩니다. 
    dp[r][c+1][(k + damage_map[r][c]) % MOD] = true;

여기서 MOD는 10007입니다.

초기 조건

시작점 (1,1)에서만 damage_map[1][1]만큼의 피해를 입으므로:

dp[1][1][damage_map[1][1]] = true;

최종 결과

최종 목적지 (n,m)에 도달했을 때, dp[n][m][k]가 true인 모든 k의 개수를 셉니다.

구현 코드

#include <iostream>
#include <vector>
#include <cstring> // for memset

const int MOD = 10007;

long long damage_map[55][55]; // 각 칸의 피해량
bool dp_path_damage[55][55][MOD]; // dp_path_damage[r][c][k] = (r,c)에 k 피해량으로 도달 가능?

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int num_rows, num_cols;
    std::cin >> num_rows >> num_cols;

    for (int r = 1; r <= num_rows; ++r) {
        for (int c = 1; c <= num_cols; ++c) {
            std::cin >> damage_map[r][c];
            // 각 칸의 피해량도 미리 MOD로 나눈 나머지로 저장하여 계산 간소화
            damage_map[r][c] %= MOD;
        }
    }

    // 시작점 (1,1) 초기화: damage_map[1][1]만큼의 피해로 도달 가능
    dp_path_damage[1][1][damage_map[1][1]] = true;

    // DP 테이블 채우기
    for (int r = 1; r <= num_rows; ++r) {
        for (int c = 1; c <= num_cols; ++c) {
            for (int k = 0; k < MOD; ++k) {
                if (dp_path_damage[r][c][k]) { // 현재 (r,c)에 k 피해량으로 도달 가능하다면
                    // 아래쪽 (r+1, c)로 이동
                    if (r + 1 <= num_rows) {
                        int next_damage_mod = (k + damage_map[r+1][c]) % MOD;
                        dp_path_damage[r+1][c][next_damage_mod] = true;
                    }
                    // 오른쪽 (r, c+1)로 이동
                    if (c + 1 <= num_cols) {
                        int next_damage_mod = (k + damage_map[r][c+1]) % MOD;
                        dp_path_damage[r][c+1][next_damage_mod] = true;
                    }
                }
            }
        }
    }

    // 최종 목적지 (num_rows, num_cols)에서 가능한 서로 다른 피해량 나머지 개수 세기
    int distinct_damage_counts = 0;
    for (int k = 0; k < MOD; ++k) {
        if (dp_path_damage[num_rows][num_cols][k]) {
            distinct_damage_counts++;
        }
    }

    std::cout << distinct_damage_counts << std::endl;

    return 0;
}

3차원 동적 계획법

3차원 동적 계획법(3D DP)은 문제의 상태를 세 개의 변수로 표현하여 해결하는 동적 계획법의 한 형태입니다. 이는 2차원 DP가 두 개의 변수를 사용하는 것과 유사하며, 주로 공간적 차원이나 추가적인 상태 정보를 다룰 때 유용합니다.

3차원 DP의 핵심 원리

3차원 DP는 dp[x][y][z]와 같이 3차원 배열을 사용하여 중간 계산 결과를 저장합니다. 각 차원은 문제의 특정 변수나 상태를 나타냅니다. 예를 들어, 격자 상에서 (x,y) 위치에 도달했을 때 z라는 추가 조건(예: 누적된 값, 사용한 아이템 개수 등)을 만족하는 최적 해를 구하는 데 사용될 수 있습니다. 상태 전이식은 이전 상태들로부터 현재 dp[x][y][z] 값을 계산하는 방법을 정의합니다.

구현 단계

  1. DP 배열 정의:

    int dp[dim1][dim2][dim3] 또는 std::vector<std::vector<std::vector<int>>>와 같은 3차원 배열을 선언합니다. 각 차원의 크기는 문제의 제약 조건에 맞게 설정합니다.

  2. 경계 조건 초기화:

    DP 배열의 가장 기본적인 상태들을 초기화합니다. 이는 문제의 출발점이나 가장 단순한 경우에 해당합니다.

  3. DP 배열 채우기:

    세 개의 중첩 반복문을 사용하여 DP 배열의 각 셀을 순회합니다. 각 dp[x][y][z]는 이전의 계산된 dp 값들과 상태 전이식에 따라 갱신됩니다.

  4. 결과 도출:

    최종 결과는 3차원 DP 테이블의 특정 위치(예: 가장 큰 인덱스에 해당하는 셀)에서 얻거나, 모든 가능한 최종 상태를 탐색하여 최적의 값을 찾습니다.

적용 시나리오

  • 경로 탐색 문제 (추가 제약 조건 포함):

    미궁 탈출 문제(위 T4 문제)와 같이 (x,y) 위치에 도달했을 때 특정 누적 값을 추적해야 하는 경우 (예: 누적 피해량의 나머지, 사용한 열쇠의 개수 등).

  • 최적화 문제 (3차원 공간):

    3D 격자에서 최단 경로, 최대 가치 등을 찾는 문제.

  • 게임 이론 (플레이어 상태):

    두 명의 플레이어와 턴 기반 게임에서 각 플레이어의 현재 상태를 (x,y)로, 게임의 진행도를 z로 나타내는 경우.

주의사항

  • 메모리 사용량: 3차원 DP 배열은 1차원 또는 2차원 배열보다 훨씬 많은 메모리를 소모할 수 있습니다. O(dim1 × dim2 × dim3)의 공간 복잡도를 가지므로, 차원 크기가 너무 크지 않도록 주의해야 합니다.
  • 상태 전이식의 복잡성: 세 변수 간의 관계를 정확히 모델링하는 상태 전이식을 수립하는 것이 중요합니다.

3차원 DP는 상태 공간이 세 변수로 정의될 때 복잡한 문제에 대한 체계적인 해결책을 제공합니다.

숫자 이어붙이기 문제

문제 설명

한 줄로 나열된 숫자 시퀀스가 다음 조건을 만족할 때, 이를 "이어붙이기 시퀀스"라고 부릅니다:

  • 인접한 두 숫자 쌍에 대해, 앞 숫자의 1의 자리가 뒷 숫자의 최고 자리와 같습니다.

이제 길이 n인 숫자 시퀀스 a1, a2, ..., an이 주어집니다. 여러분은 이 시퀀스에서 일부 숫자를 삭제할 수 있습니다 (하나도 삭제하지 않아도 됩니다). 남은 숫자들은 원래의 상대적 순서를 유지해야 합니다.

남은 숫자들이 정확히 "이어붙이기 시퀀스"를 이루도록 만들기 위해 최소한으로 삭제해야 할 숫자의 개수를 계산하여 출력하세요.

문제 해결 전략

이 문제는 "가장 긴 이어붙이기 부분 수열(Longest Dragon Subsequence)"을 찾는 문제로 변환할 수 있습니다. 가장 긴 부분 수열을 찾으면, 전체 시퀀스 길이에서 그 부분 수열의 길이를 뺀 값이 최소 삭제 숫자의 개수가 됩니다.

이것은 전형적인 1차원 동적 계획법 문제입니다. DP 상태를 다음과 같이 정의합니다:

  • max_len_ending_with_digit[d]: 마지막 숫자의 1의 자리가 d인 이어붙이기 부분 수열의 최대 길이.

각 숫자 a[i]에 대해, 그 숫자의 최고 자리 L과 1의 자리 R을 구합니다. 이 a[i]는 최고 자리가 L인 숫자이므로, 1의 자리가 L이었던 이전 부분 수열에 이어붙여질 수 있습니다. 따라서, a[i]를 포함하는 이어붙이기 부분 수열의 길이는 max_len_ending_with_digit[L] + 1이 됩니다. 이 값으로 max_len_ending_with_digit[R]을 갱신합니다.

상태 전이식

각 숫자 current_num에 대해:

  • first_digit = get_first_digit(current_num)
  • last_digit = current_num % 10
  • max_len_ending_with_digit[last_digit] = max(max_len_ending_with_digit[last_digit], max_len_ending_with_digit[first_digit] + 1)

max_len_ending_with_digit 배열은 모두 0으로 초기화합니다. 각 숫자는 자기 자신만으로도 길이 1의 이어붙이기 수열이 될 수 있으므로, 어떤 first_digit에서 시작하더라도 max_len_ending_with_digit[first_digit] + 1은 최소 1이 됩니다.

최종 결과

max_len_ending_with_digit 배열의 모든 값 중에서 최대값을 찾습니다. 이 값이 가장 긴 이어붙이기 부분 수열의 길이가 됩니다. 최종 답은 총 숫자 개수 - 최장 부분 수열 길이입니다.

구현 코드

#include <iostream>
#include <vector>
#include <algorithm> // for std::max

// 숫자의 최고 자리를 반환하는 헬퍼 함수
int get_first_digit(int num) {
    while (num >= 10) {
        num /= 10;
    }
    return num;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n;
    std::cin >> n;

    std::vector<int> numbers(n);
    std::vector<int> first_digits(n);
    std::vector<int> last_digits(n);

    for (int i = 0; i < n; ++i) {
        std::cin >> numbers[i];
        first_digits[i] = get_first_digit(numbers[i]);
        last_digits[i] = numbers[i] % 10;
    }

    // dp_max_len[d]: 1의 자리가 d인 숫자로 끝나는 가장 긴 이어붙이기 시퀀스의 길이
    // 인덱스는 0부터 9까지의 숫자
    std::vector<int> dp_max_len(10, 0); 

    // 각 숫자에 대해 DP 업데이트
    for (int i = 0; i < n; ++i) {
        int current_first_digit = first_digits[i];
        int current_last_digit = last_digits[i];
        
        // 현재 숫자는 (1의 자리가 current_first_digit인 숫자들로 끝나는 시퀀스) + 현재 숫자
        // 또는 단독으로 현재 숫자로 시작하는 새로운 시퀀스가 될 수 있다.
        // 현재 숫자로 끝나는 시퀀스의 길이는 dp_max_len[current_last_digit]와
        // dp_max_len[current_first_digit] + 1 중 큰 값이 된다.
        dp_max_len[current_last_digit] = std::max(dp_max_len[current_last_digit], dp_max_len[current_first_digit] + 1);
    }

    // 모든 dp_max_len 값 중 최대값을 찾아 최장 이어붙이기 부분 수열의 길이를 얻는다.
    int longest_sequence_length = 0;
    for (int i = 0; i < 10; ++i) {
        longest_sequence_length = std::max(longest_sequence_length, dp_max_len[i]);
    }

    // 최소 삭제 숫자의 개수 = 전체 숫자 개수 - 최장 이어붙이기 부분 수열의 길이
    std::cout << n - longest_sequence_length << std::endl;

    return 0;
}

직속 상사 없는 회식 문제

문제 설명

한 회사에서 회식을 준비하고 있습니다. 그런데 직원들은 자신의 직속 상사와는 같은 테이블에 앉고 싶어 하지 않습니다.

인사 담당자로서 여러분은 각 직원의 직속 상사가 누구인지 알고 있습니다 (사장만 상사가 없습니다). 직원들은 1번부터 n번까지 번호가 매겨져 있습니다.

사장(1번)을 포함하여 가능한 한 많은 직원을 회식에 초대하고 싶지만, 다음 조건을 만족해야 합니다:

  • 어떤 직원의 직속 상사가 회식에 참석하면, 그 직원은 참석할 수 없습니다 (그 반대도 마찬가지입니다).

회식에 초대할 수 있는 최대 인원 수를 출력하세요.

문제 해결 전략

이 문제는 트리 구조에서 "최대 독립 집합(Maximum Independent Set)"을 찾는 문제에 해당합니다. 트리의 각 노드는 직원, 간선은 직속 상사-부하 직원 관계를 나타냅니다. 독립 집합은 서로 인접하지 않는 노드들의 집합이며, 최대 독립 집합은 노드의 개수가 최대인 독립 집합입니다.

트리 DP(동적 계획법)를 사용하여 이 문제를 해결합니다. 각 노드 u에 대해 두 가지 상태를 정의합니다:

  • dp[u][0]: 노드 u를 선택하지 않았을 때(회식에 초대하지 않았을 때) u를 루트로 하는 서브트리에서 얻을 수 있는 최대 초대 인원 수.
  • dp[u][1]: 노드 u를 선택했을 때(회식에 초대했을 때) u를 루트로 하는 서브트리에서 얻을 수 있는 최대 초대 인원 수.

상태 전이식

깊이 우선 탐색(DFS)을 통해 리프 노드에서부터 루트 노드로 정보를 전달합니다.

  • 노드 u를 선택하지 않을 때 (dp[u][0]):

    노드 u를 선택하지 않으면, u의 자식 노드들은 선택해도 되고 선택하지 않아도 됩니다. 따라서 각 자식 노드 v에 대해 max(dp[v][0], dp[v][1]) 값을 모두 더합니다.

    dp[u][0] = \sum_{v \in children(u)} \max(dp[v][0], dp[v][1])
  • 노드 u를 선택할 때 (dp[u][1]):

    노드 u를 선택하면, u의 직속 부하 직원들(자식 노드들)은 선택할 수 없습니다. 따라서 각 자식 노드 v에 대해 dp[v][0] 값을 모두 더하고, u 자신을 포함하므로 1을 더합니다.

    dp[u][1] = 1 + \sum_{v \in children(u)} dp[v][0]

최종 결과

최종적으로 루트 노드(사장, 1번 노드)에 대해 max(dp[1][0], dp[1][1])을 계산하여 출력합니다.

구현 코드

#include <iostream>
#include <vector>
#include <algorithm> // for std::max

// dp_memo[u][0]: 노드 u를 선택하지 않았을 때의 최대 인원
// dp_memo[u][1]: 노드 u를 선택했을 때의 최대 인원
long long dp_memo[1000005][2];
std::vector<int> adj_list[1000005]; // 트리의 인접 리스트 (부하 직원 -> 상사 관계를 역전하여 자식 -> 부모로 저장)

// DFS를 통해 트리 DP 수행
void dfs_tree_dp(int current_node) {
    long long sum_if_parent_not_chosen = 0; // 현재 노드가 선택되지 않았을 때 자식들의 최대값 합
    long long sum_if_parent_chosen = 0;   // 현재 노드가 선택되었을 때 자식들이 선택되지 않은 값의 합

    // 모든 자식 노드에 대해 재귀적으로 DFS 호출
    for (int child_node : adj_list[current_node]) {
        dfs_tree_dp(child_node);
        // current_node를 선택하지 않은 경우: 자식은 선택되거나 안 되거나 둘 다 가능
        sum_if_parent_not_chosen += std::max(dp_memo[child_node][0], dp_memo[child_node][1]);
        // current_node를 선택한 경우: 자식은 반드시 선택되지 않아야 함
        sum_if_parent_chosen += dp_memo[child_node][0];
    }

    dp_memo[current_node][0] = sum_if_parent_not_chosen; // 현재 노드 선택 안 함
    dp_memo[current_node][1] = sum_if_parent_chosen + 1; // 현재 노드 선택 (+1은 자기 자신)
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int num_employees;
    std::cin >> num_employees;

    std::vector<bool> is_child_node(num_employees + 1, false); // i번 노드가 어떤 노드의 자식인지 (상사 여부 판단)

    // 입력은 a의 직속 상사가 b라고 주어지므로, b -> a 관계를 저장하여 트리를 만든다.
    // 즉, b가 부모, a가 자식이 된다.
    for (int i = 0; i < num_employees - 1; ++i) {
        int subordinate, superior;
        std::cin >> subordinate >> superior;
        adj_list[superior].push_back(subordinate); // superior가 부모, subordinate가 자식
        is_child_node[subordinate] = true; // subordinate는 자식 노드임
    }

    int root_node_id = 0;
    // 사장은 상사가 없는 유일한 사람 (즉, 어떤 노드의 자식도 아님)
    for (int i = 1; i <= num_employees; ++i) {
        if (!is_child_node[i]) {
            root_node_id = i;
            break;
        }
    }

    dfs_tree_dp(root_node_id);

    // 루트 노드(사장)를 선택했을 때와 선택하지 않았을 때 중 최대값
    std::cout << std::max(dp_memo[root_node_id][1], dp_memo[root_node_id][0]) << std::endl;

    return 0;
}

트리 동적 계획법 (Tree DP)

트리 동적 계획법(Tree DP)은 트리와 같은 계층적 구조를 활용하여 상태 전이를 수행하는 동적 계획법 기법입니다. 주로 트리 구조에서 최적화 문제를 해결하는 데 사용됩니다.

트리 DP의 핵심 아이디어

트리 DP는 주로 후위 순회(post-order traversal) 또는 깊이 우선 탐색(DFS)을 통해 트리의 구조를 탐색합니다. 이 과정에서 리프 노드에서부터 루트 노드 방향으로 정보를 전달하며, 각 노드의 상태는 해당 노드의 자식 노드들의 상태로부터 결정됩니다. 일반적으로 dp[u][k]는 노드 u를 루트로 하는 서브트리에서 상태 k일 때의 최적 해를 나타냅니다.

구현 단계

  1. 상태 정의 및 전이식 수립:

    예를 들어, 이진 트리에서 최대 경로 합을 찾는 문제를 생각해봅시다.

    • 상태 정의: dp[u]는 노드 u를 포함하며 u에서 시작하여 아래로 뻗어나가는 최대 경로 합입니다.
    • 전이식: dp[u] = u.val + max(dp[u.left], dp[u.right], 0) (음수 경로는 선택하지 않음).
  2. DFS 재귀 구현:

    DFS 함수를 사용하여 트리를 탐색하고, 재귀적으로 자식 노드들의 DP 값을 계산한 후 현재 노드의 DP 값을 업데이트합니다.

    #include <algorithm> // for std::max
#include <functional> // for std::function
#include <limits>     // for std::numeric_limits

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

int calculateMaxPathSum(TreeNode* root) {
    int max_overall_sum = std::numeric_limits<int>::min(); // 전체 트리의 최대 경로 합

    // 재귀 DFS 함수 정의
    std::function<int(TreeNode*)> dfs_post_order = 
        [&](TreeNode* current_node) -> int {
        if (!current_node) {
            return 0; // null 노드의 기여는 0
        }

        // 왼쪽 및 오른쪽 자식 서브트리의 최대 경로 합 (음수는 0으로 처리하여 경로에 포함시키지 않음)
        int left_sum = std::max(0, dfs_post_order(current_node->left));
        int right_sum = std::max(0, dfs_post_order(current_node->right));

        // 현재 노드를 경로의 '최고점'으로 포함하는 경로 합 업데이트 (전역 변수)
        max_overall_sum = std::max(max_overall_sum, current_node->val + left_sum + right_sum);

        // 현재 노드를 포함하여 위로 뻗어나갈 수 있는 최대 경로 합 반환
        return current_node->val + std::max(left_sum, right_sum);
    };

    dfs_post_order(root);
    return max_overall_sum;
}

대표적인 문제 유형

  • 트리 최대 독립 집합:

    각 노드 u에 대해 두 가지 상태를 정의합니다:

    • dp[u][0]: 노드 u를 선택하지 않았을 때의 최대 가치.
    • dp[u][1]: 노드 u를 선택했을 때의 최대 가치.

    전이식은 다음과 같습니다 (자식 노드 v에 대해):

    dp[u][0] += std::max(dp[v][0], dp[v][1]);
dp[u][1] += dp[v][0];
  • 트리 최장 경로 (지름):

    각 노드에서 가장 깊은 경로를 기록하면서, 동시에 두 자식 경로를 합쳐서 현재 노드를 지나는 최장 경로를 업데이트합니다.

    int tree_diameter = 0;
std::function<int(TreeNode*)> dfs_diameter = 
    [&](TreeNode* u) -> int {
    if (!u) return 0;
    int left_depth = dfs_diameter(u->left);
    int right_depth = dfs_diameter(u->right);
    tree_diameter = std::max(tree_diameter, left_depth + right_depth); // 현재 노드를 지나는 경로
    return 1 + std::max(left_depth, right_depth); // 현재 노드 포함 최대 깊이
};

주의사항

  • 트리 DP는 재귀를 통해 구현되는 경우가 많으므로, 깊은 트리에서는 스택 오버플로우에 주의해야 합니다. (비재귀 DFS로 대체 가능)
  • 다지 트리(multi-way tree)의 경우, 모든 자식 노드를 순회하며 상태 전이를 계산해야 합니다.
  • 리프 노드의 초기화는 문제 요구사항에 따라 적절하게 설정해야 합니다.

시간 및 공간 복잡도

트리 DP의 시간 복잡도는 일반적으로 노드 수 N에 비례하는 O(N)입니다. 각 노드가 한 번만 방문되기 때문입니다. 공간 복잡도는 상태의 차원에 따라 O(N) 또는 O(N2)이 될 수 있습니다.

P1352: 상사 없는 파티

문제 설명

어느 대학에 1번부터 n번까지 번호가 매겨진 n명의 직원이 있습니다.

이들 사이에는 종속 관계가 존재하며, 그들의 관계는 총장을 뿌리로 하는 트리와 같습니다. 부모 노드는 자식 노드의 직속 상사입니다.

현재 연례 기념 파티가 열리며, 파티에 한 명의 직원을 초대할 때마다 행복 지수 ri가 증가합니다. 하지만 어떤 직원의 직속 상사가 파티에 참석하면, 그 직원은 어떤 일이 있어도 파티에 참석하지 않으려 합니다.

따라서, 가장 높은 행복 지수를 얻기 위해 어떤 직원들을 초대해야 하는지 계산하고, 그 최대 행복 지수를 출력하는 프로그램을 작성하세요.

문제 해결 전략

이 문제는 앞서 다룬 "직속 상사 없는 회식 문제"와 동일한 트리 DP 문제이지만, 최대 인원 수가 아닌 최대 행복 지수를 구해야 합니다. 또한, 문제에서 직접 루트 노드가 누구인지 알려주지 않으므로, 이를 찾아내는 과정이 필요합니다.

DP 상태 정의는 동일합니다:

  • dp[u][0]: 노드 u를 선택하지 않았을 때, u를 루트로 하는 서브트리에서 얻을 수 있는 최대 행복 지수.
  • dp[u][1]: 노드 u를 선택했을 때, u를 루트로 하는 서브트리에서 얻을 수 있는 최대 행복 지수.

상태 전이식은 거의 동일하지만, dp[u][1]을 계산할 때 인원 수 1을 더하는 대신, 노드 u의 행복 지수 r[u]를 더해야 합니다.

  • 노드 u를 선택하지 않을 때 (dp[u][0]): dp[u][0] = \sum_{v \in children(u)} \max(dp[v][0], dp[v][1])
  • 노드 u를 선택할 때 (dp[u][1]): dp[u][1] = r[u] + \sum_{v \in children(u)} dp[v][0]

루트 노드를 찾는 방법은, 모든 직원 중 누구의 부하 직원도 아닌 직원(즉, 어떤 직원의 자식도 아닌 직원)을 찾는 것입니다. 이 직원이 트리의 루트(총장)가 됩니다.

구현 코드

#include <iostream>
#include <vector>
#include <algorithm> // for std::max
#include <cstring>   // for memset

// dp_memo[u][0]: 노드 u를 선택하지 않았을 때의 최대 행복 지수
// dp_memo[u][1]: 노드 u를 선택했을 때의 최대 행복 지수
long long dp_memo[1000005][2];
long long happiness_scores[1000005]; // 각 직원의 행복 지수
std::vector<int> adj_list[1000005]; // 트리의 인접 리스트 (부모 -> 자식 관계)
bool has_superior[1000005]; // 각 직원이 상사를 가지고 있는지 여부 (루트 찾기 위함)

// DFS를 통한 트리 DP 계산
void dfs_tree_dp_happiness(int current_node) {
    long long sum_child_max_happiness = 0; // 현재 노드가 선택되지 않았을 때 자식들의 (선택/미선택) 최대 행복 지수 합
    long long sum_child_no_select_happiness = 0; // 현재 노드가 선택되었을 때 자식들이 선택되지 않은 행복 지수 합

    for (int child_node : adj_list[current_node]) {
        dfs_tree_dp_happiness(child_node); // 자식 노드 먼저 계산
        sum_child_max_happiness += std::max(dp_memo[child_node][0], dp_memo[child_node][1]);
        sum_child_no_select_happiness += dp_memo[child_node][0];
    }

    dp_memo[current_node][0] = sum_child_max_happiness; // 현재 노드 선택 안 함
    dp_memo[current_node][1] = sum_child_no_select_happiness + happiness_scores[current_node]; // 현재 노드 선택 (+ 자신의 행복 지수)
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int num_employees;
    std::cin >> num_employees;

    // 각 직원의 행복 지수 입력
    for (int i = 1; i <= num_employees; ++i) {
        std::cin >> happiness_scores[i];
    }

    // 상사-부하 관계 입력 및 트리 구성
    // l은 k의 직속 상사
    for (int i = 0; i < num_employees - 1; ++i) {
        int subordinate_id, superior_id;
        std::cin >> subordinate_id >> superior_id;
        adj_list[superior_id].push_back(subordinate_id); // superior가 부모, subordinate가 자식
        has_superior[subordinate_id] = true; // 이 직원은 상사가 있음
    }

    // 루트 노드(상사가 없는 유일한 직원) 찾기
    int root_id = 0;
    for (int i = 1; i <= num_employees; ++i) {
        if (!has_superior[i]) {
            root_id = i;
            break;
        }
    }

    // 루트 노드부터 DFS 시작
    dfs_tree_dp_happiness(root_id);

    // 루트 노드를 선택했을 때와 선택하지 않았을 때의 최대 행복 지수 중 더 큰 값 출력
    std::cout << std::max(dp_memo[root_id][1], dp_memo[root_id][0]) << std::endl;

    return 0;
}

태그: DynamicProgramming TreeDP gcd MaximumIndependentSet Pathfinding

7월 18일 01:44에 게시됨

인기 태그

©2026 괴물 클럽