동적 계획법으로 게임 목표 점수에 도달하는 방법의 수 세기

플레이어가 한 번의 이동마다 3점, 5점 또는 10점을 얻을 수 있는 게임이 있다고 가정해 봅시다. 목표 점수가 주어졌을 때, 우리의 과제는 이 세 가지 점수 조합을 사용하여 해당 목표 점수에 도달할 수 있는 경우의 수를 구하는 것입니다.

이 문제는 동적 계획법(Dynamic Programming)으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 0부터 n까지의 모든 점수 값에 대한 경우의 수를 저장하는 테이블을 만들고, 3, 5, 10 각각의 점수를 순서대로 적용하며 테이블을 갱신하는 것입니다.

입력 및 출력

입력:
3, 5, 10을 사용하여 도달할 최대 점수. 입력값이 50이라고 가정합니다.
출력:
(3, 5, 10)을 사용하여 50에 도달하는 방법의 수: 14

알고리즘

가능한 점수는 3, 5, 10 세 가지뿐입니다.

입력: n은 도달해야 할 최대 점수입니다.

출력: 점수 n에 도달할 수 있는 가능한 방법의 수입니다.

Begin
   create table of size n+1
   set all table entries to 0
   table[0] := 1

   for i := 3 to n, do
      table[i] := table[i] + table[i-3]
   done

   for i := 5 to n, do
      table[i] := table[i] + table[i-5]
   done

   for i := 10 to n, do
      table[i] := table[i] + table[i-10]
   done

   return table[n]
End

알고리즘 동작 원리

table[0] = 1로 초기화하는 이유는, 점수 0에 도달하는 방법은 아무것도 선택하지 않는 단 한 가지뿐이기 때문입니다. 그다음 각 점수(3, 5, 10)별로 순회하면서 현재 점수 i를 만들기 위해 직전 상태(table[i-3], table[i-5], table[i-10])의 경우의 수를 더해 줍니다. 점수 종류별로 바깥 루프를 돌기 때문에 순서가 다른 같은 조합(예: 3+5와 5+3)은 중복으로 세지 않습니다.

C++ 구현 예제

#include <iostream>
using namespace std;

// 점수 n에 도달하는 방법의 수를 반환하는 함수
int countWay(int n) {
   int table[n+1], i;   // 각 점수 값별 경우의 수를 저장할 테이블

   for(int i = 0; i<=n; i++) {
      table[i] = 0;   // 모든 테이블 값을 0으로 초기화
   }

   table[0] = 1;      // 점수 0에 도달하는 방법은 1가지
   for (i=3; i<=n; i++)   // 3점을 사용하는 경우
      table[i] += table[i-3];

   for (i=5; i<=n; i++)   // 5점을 사용하는 경우
      table[i] += table[i-5];

   for (i=10; i<=n; i++)   // 10점을 사용하는 경우
      table[i] += table[i-10];

   return table[n];
}

int main() {
   int n;
   cout << "최대 점수 입력: ";
   cin >> n;
   cout << "(3, 5, 10)을 사용하여 " << n <<"에 도달하는 방법의 수: " << countWay(n);
}

실행 결과

최대 점수 입력: 50
(3, 5, 10)을 사용하여 50에 도달하는 방법의 수: 14

시간 복잡도 분석

이 알고리즘은 세 개의 반복문을 각각 한 번씩 순회하므로 시간 복잡도는 O(n)이며, 크기가 n+1인 테이블을 사용하므로 공간 복잡도 역시 O(n)입니다. 완전 탐색으로 모든 조합을 일일이 확인하는 지수 시간 복잡도 방식과 비교하면, 동적 계획법을 활용하면 매우 큰 목표 점수에 대해서도 빠르게 답을 구할 수 있다는 장점이 있습니다.