21735 c++ - 눈덩이 굴리기

백트래킹 문제입니다. 또는 DP로도 풀 수 있습니다.

[Swift] BackTracking / 백트래킹 / 퇴각검색

 

[종만북] Dynamic Programming / DP / 동적 계획법

 

처음에 끝에 도달한 경우에 대해서 기저조건을 설정해 두지 않아서 틀렸습니다. m의 크기가 작아서 그냥 dfs로 모든 경우를 백트래킹으로 풀었습니다. dfs로 푼 이후에, DP로도 풀 수 있을 거 같아서 풀어보고 나서 둘의 차이점에 대해서 생각해 보았습니다.

DFS와 DP의 차이

• DFS:
  • 재귀 호출을 통해 모든 가능한 경로를 탐색하면서 최적해를 찾습니다.
  • 특정 경로가 중복될 가능성이 높아, 같은 계산을 반복하게 됩니다. 이를 방지하기 위해 메모이제이션을 추가할 수 있지만, 재귀 깊이가 깊어지면 스택 오버플로우가 발생할 수 있습니다.
  • 시간 복잡도: 모든 경로를 탐색하므로 최악의 경우 O(2^M)이 됩니다. (경우의 수는 각 초마다 2가지 선택을 하기 때문)
• DP (Bottom-Up):
  • DP에서는 현재 가능한 상태들(dp[d][i])을 순차적으로 갱신하며, 이전 단계의 최적해를 재활용하여 중복 계산을 피합니다.
  • 재귀 호출이 없어 스택 오버플로우가 발생하지 않습니다.
  • 시간 복잡도: 모든 상태를 한번씩만 계산하므로 O(N * M)이 됩니다. DFS에 비해 훨씬 효율적입니다.

요약

• DFS는 재귀적으로 모든 경로를 탐색하는 방식이며, Bottom-Up DP는 중복 계산을 피하고 한 번의 순차적 계산으로 최적해를 찾는 방식입니다. O(N*M) > O(2^M)
• Bottom-Up DP 방식은 DFS 대비 더 효율적이며, 특히 M이 클수록 성능 차이가 더 커집니다.

따라서 이 문제의 경우, DP 방식이 훨씬 빠르고 메모리 사용도 효율적입니다. m의 범위가 10보다 더 컸으면 그냥 dfs로는 못풀었을 겁니다.

 

백트래킹으로 푼 해답.

#include <algorithm>
#include <iostream>
#include <vector>

#define FASTIO ios::sync_with_stdio(0), cin.tie(0)
using namespace std;

int n, m, maxCount = 0;

void dfs(vector<int> a, int d, int i, int sum) {
  if (d == m || i >= n) {
    maxCount = max(sum, maxCount);
    return;
  }

  dfs(a, d + 1, i + 1, sum + a[i + 1]);
  dfs(a, d + 1, i + 2, sum / 2 + a[i + 2]);
}

int main() {
  FASTIO;

  cin >> n >> m;
  vector<int> a(n + 1, 0);
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }

  dfs(a, 0, 0, 1);

  cout << maxCount;

  return 0;
}

 

DP로 푼 해답. Bottom UP방식으로 풀면된다.

#include <algorithm>
#include <iostream>
#include <vector>

#define FASTIO ios::sync_with_stdio(0), cin.tie(0)
using namespace std;

int main() {
  FASTIO;

  int n, m;
  cin >> n >> m;
  vector<int> a(n + 1, 0);
  vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }

  dp[0][0] = 1;
  int maxCount = 0;

  for (int d = 1; d <= m; d++) {
    for (int i = 0; i <= n; i++) {
      if (dp[d - 1][i] == 0) continue;

      if (i == n) {
        maxCount = max(maxCount, dp[d - 1][i]);
        continue;
      }

      if (i + 1 <= n) 
        dp[d][i + 1] = max(dp[d][i + 1], dp[d - 1][i] + a[i + 1]);
      if (i + 2 <= n)
        dp[d][i + 2] = max(dp[d][i + 2], dp[d - 1][i] / 2 + a[i + 2]);
    }
  }

  for (int i = 1; i <= n; i++) {
    maxCount = max(maxCount, dp[m][i]);
  }

  cout << maxCount;

  return 0;
}