[Jungol] 정올 1169 주사위 던지기1

출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=449&sca=20

Approach

주사위를 3번 던져서 나올 수 있는 모든 경우의 수

for(int i=1; i<=6; i++){
    for(int j=1; j<=6; j++){
        for(int k=1; k<=6; k++){
            printf("%d %d %d\n", i, j, k);

 

반복문을 대신하는 재귀함수

void dice(int step){
    if(step > N){ // step이 N번 초과하면 출력하고 리턴
        output();
        return;
    }
    for(int i=1; i<=6; i++){
        arr[step] = i;
        dice(step + 1);
    }
}

 

중복되는 조합을 제거하는 방법

이전에 나온 수보다 작은 수가 나오면 중복 발생

ex) (2, 1)과 (1, 2)는 중복됩니다.

따라서 주사위를 1부터가 아닌 직전에 나온 수(arr[step - 1]) 부터 시작하면 됩니다.

첫번째는 1부터 시작해야 하므로 arr[0]을 1로 초기화하면 됩니다.

for (int i = arr[step - 1]; i <= 6; i++) {
    arr[step] = i;
    dice(step + 1);
}

　

주사위의 눈이 모두 다른 수가 나오는 경우

방문 표시할 수 있는 배열 이용해서 이미 체크된 수는 다시 넣지 않습니다.

(배열에서 제거될 때에는 다시 체크 해제)

for (int i = 1; i <= 6; i++) {
    if (chk[i]) continue;
    chk[i] = 1;
    arr[step] = i;
    dice(step + 1);
    chk[i] = 0;
}

---

#include <stdio.h>
 
int N, M, arr[10], chk[10];
 
void output() {
    for (int i = 1; i <= N; i++)
        printf("%d ", arr[i]);
    printf("\n");
}
 
void dice1(int step) {
    if (step > N) {
        output();
        return;
    }
 
    for (int i = 1; i <= 6; i++) {
        arr[step] = i;
        dice1(step + 1);
    }
}
 
void dice2(int step) {
    if (step > N) {
        output();
        return;
    }
 
    for (int i = arr[step - 1]; i <= 6; i++) {
        arr[step] = i;
        dice2(step + 1);
    }
}
 
void dice3(int step) {
    if (step > N) {
        output();
        return;
    }
 
    for (int i = 1; i <= 6; i++) {
        if (chk[i]) continue;
        chk[i] = 1;
        arr[step] = i;
        dice3(step + 1);
        chk[i] = 0;
    }
}
 
int main() {
    scanf("%d %d", &N, &M);
    arr[0] = 1;
    if (M == 1) dice1(1);
    else if (M == 2) dice2(1);
    else dice3(1);
    return 0;
}