기초다지기 함수3-형성평가3(C++)

233 : 함수3 - 형성평가3

제한시간: 1000 ms    메모리제한: 0 MB
해결횟수: 612 회    시도횟수: 1235 회   

자연수 N과 M을 입력받아서 주사위를 N번 던져서 나온 눈의 합이 M이 나올 수 있는 모든 경우를 출력하는 프로그램을 작성하시오. 
단, N은 10 이하의 정수이다.

[Copy] 3 10

[Copy] 1 3 6 1 4 5 1 5 4 1 6 3 2 2 6 2 3 5 … 6 2 2 6 3 1

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54

/**************************************************************     Problem: 233     User: a132034     Language: C++     Result: Success     Time:575 ms     Memory:1740 kb ****************************************************************/     #include    <iostream> using namespace std;   static int sum[10]; static int loc = 0;   void dice(int N, int M) {     for (int i = 1; i <= 6; ++i)     {         sum[loc] = i;           if (loc == N - 1)         {             int total = 0;             for (int j = 0; j <= loc; ++j)                 total += sum[j];               if (total == M)             {                 for (int k = 0; k < N; ++k)                     cout << sum[k] << " ";                 cout << endl;                 return;             }         }         else         {             loc++;             dice(N, M);             loc--;         }     } }   int main() {     int N, M;     cin >> N >> M;       dice(N, M);       return 0; }

혹시나 해서 기초다지기중에 안푼게 있나 살펴보다가 아직 안푼게 있다는걸 확인. 

문제를 봤더니 기초다지기 수준보다는 약간 실력키우기 수준같기도 하고.. 어려웠다. 

[도움말 접기]

재귀함수에 레벨(level)과 합계(sum) 두 개의 인수를 전달하여 sum이 M과 같은 경우에만 출력하도록 한다.
(정의 : void dice(int level  int sum)  호출 : dice(level+1  sum+i))

도움말을 보고 풀려고 dice 함수를 만들기는 했는데.. 

도움말과는 전혀 다른 방법으로 풀었다. 

backtracking을 이용하여 풀었는데.. 도움말대로 풀면 시간이 좀더 줄지 않을까 생각해본다... 생각이 난다면 도움말같은 방법으로도 한번 풀어봐야겠다. 

푼 방법은 간단하다. 

주사위는 최대 10개까지 입력되므로 10개짜리 배열인 sum에 각 주사위 숫자를 저장하였고, loc변수로 다음 주사위 숫자를 저장하며 모든 경우의 수를 살펴보았다. 

보통 backtraking같은 경우 가지치기가 중요한데..(쓸데없는 연산량을 줄이기 위해..) 사실 문제에서 요구하는 수준이 그정도 수준까지는 아니라서 가지치기에 대해 깊게 생각해보지는 않았으나... 

중간에 만약 N개를 다 던지지 않았는데에도 이미 M을 초과한다던지 하는 경우에는 가지를 쳐줘도 될 것 같다.