주사위를 n번 던져 무중복 합이 k인 경우 나열하기

문제).

   n ( > 1)개의 주사위를 던졌을 때 눈들의 합이 k인 경우만 출력하는 알고리즘을 작성하라.

 

입력). n = 2, k = 7 

결과
[1, 6]
[2, 5]
[3, 4]
[4, 3]
[5, 2]
[6, 1]

입력). n = 3, k = 9

결과
[1, 2, 6]
[1, 3, 5]
[1, 4, 4]
[1, 5, 3]
[1, 6, 2]
[2, 1, 6]
[2, 2, 5]
[2, 3, 4]
[2, 4, 3]
[2, 5, 2]
[2, 6, 1]
[3, 1, 5]
[3, 2, 4]
[3, 3, 3]
[3, 4, 2]
[3, 5, 1]
[4, 1, 4]
[4, 2, 3]
[4, 3, 2]
[4, 4, 1]
[5, 1, 3]
[5, 2, 2]
[5, 3, 1]
[6, 1, 2]
[6, 2, 1]

 

답은 아래에... ↓

 

 

---

 

 

 

 

 

스스로 풀어보시고... ↓

 

 

 

 

---

 

 

 

 

 

 

아래 답과 비교해보세요. ↓

 

 

 

 

 

 

 

---

문제풀이

#include <stdio.h>

/* 최대 100개의 주사위를 선택할 수 있으며, 현재 계산하고 있는 주사위 눈의 갯수 저장 */
int dice[100];

/* 주사위의 갯수 - 입력값 */
int dice_count;

/* 주사위의 눈의 합 - 입력값*/
int dice_sum;

void calcurate(int idx);

int main(int argc, char **argv)
{
    int n1, n2, n3;
    
    scanf("%d %d", &dice_count, &dice_sum);
    
    calcurate(0);
    return 0;
}

/*
* 주사위의 눈을 계산하는 재귀 호출 함수
* 파라미터>
*    idx 
*      - 주사위의 순번
*      - 값의 범위: 0 <= idx <= (주사위개수 - 1)
*
* 동작방식
*    최초 호출은 0을 입력하여 호출 (0번째의 값이 1 ~ 6으로 변화)
*    재귀 호출로 다음번째 주사위를 1 ~ 6으로 증가 ....
*/
void calcurate(int idx)
{
    int eye_count;
    int n;
    int sum;
    
    /* idx 번째의 주사위의 눈을 1 ~ 6까지 증가 시킴 */
    for(eye_count = 1; eye_count <= 6; eye_count++) {
        dice[idx] = eye_count;
        if(idx < dice_count) {
            /* 다음 주사위 1 ~ 6으로 증가 시킴 */
            calcurate(idx + 1);
        }
        
        /* 마지막 주사위에 도달했다면 */
        if(idx == dice_count - 1) {
            sum = 0;
            /* 모든 주사위의 값을 더함 */
            for(n = 0; n < dice_count; n++) {
                sum += dice[n];
            }
            
            /* 모든 주사위의 값을 더한 것이 입력받은 합계값과 같으면 출력하기 */
            if(sum == dice_sum) {
                printf("[");
                for(n = 0; n < dice_count; n++) {
                    printf("%d", dice[n]);
                    if(n < dice_count - 1) {
                        printf(", ");
                    }
                }
                printf("]\n");
            }
        }
    }
}