게임에서 주어진 점수에 도달하는 방법의 수 세기

플레이어가 각 동작에서 3, 5 또는 10으로 점수를 얻을 수 있는 게임을 생각해 보겠습니다. 목표 점수도 부여됩니다. 우리의 임무는 이 3점으로 목표 점수에 도달할 수 있는 가능한 방법이 얼마나 많은지 찾는 것입니다.

동적 프로그래밍 방식을 사용하여 0에서 n까지의 모든 점수 목록을 만들고 3, 5, 10의 각 값에 대해 단순히 테이블을 업데이트합니다.

입력 및 출력

Input:
The maximum score to reach using 3, 5 and 10. Let the input is 50.
Output:
Number of ways to reach using (3, 5, 10)50: 14

알고리즘

countWays(n)

가능한 점수는 3개뿐이며 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

예

#include <iostream>
using namespace std;

// Returns number of ways to reach score n
int countWay(int n) {
   int table[n+1], i;    //table to store count for each value of i

   for(int i = 0; i<=n; i++) {
      table[i] = 0;    // Initialize all table values as 0
   }

   table[0] = 1;       //set for 1 for input as 0
   for (i=3; i<=n; i++)    //try to solve using 3
      table[i] += table[i-3];

   for (i=5; i<=n; i++)    //try to solve using 5
      table[i] += table[i-5];

   for (i=10; i<=n; i++)    //try to solve using 10
      table[i] += table[i-10];

   return table[n];
}

int main() {
   int n;
   cout << "Enter max score: ";
   cin >> n;
   cout << "Number of ways to reach using (3, 5, 10)" << n <<": " << countWay(n);
}

출력

Enter max score: 50
Number of ways to reach using (3, 5, 10)50: 14