정올 1169번: 주사위 던지기1

문제

문제 바로가기> 정올 1169번: 주사위 던지기1

JUNGOL

 

풀이

각각 중복순열, 중복조합, 순열을 구현하는 문제이다.

오랜만에 풀어보니 약간 헷갈.. 렸다 ㅎㅎ

 

순열: 서로 다른 n개 중에서 r개를 선택하여 일렬로 세우는 경우

중복순열: 서로 다른 n개 중에서 중복을 허락하고 r개를 일렬로 나열하는 수

조합: 서로 다른 n개 중에서 r개를 선택하여 그룹을 만드는 경우 (순서 상관 x)

중복조합: 서로 다른 n개 중에서 순서를 생각하지 않고 중복을 허락하여 r개를 선택하는 경우

#include<iostream>
#define MAX 7
using namespace std;

int N, M;
int seq[MAX];
bool visited[MAX];

void input(){
    cin >> N >> M;
}

void duplicatePermutation(int cnt){
    if(cnt == N){
        for(int i=0; i<N; i++) cout << seq[i] << " ";
        cout << "\n";
        return ;
    }
    for(int num=1; num<=6; num++){
        seq[cnt] = num;
        duplicatePermutation(cnt+1);
    }
}

void duplicateCombination(int idx, int cnt){
    if(cnt == N){
        for(int i=0; i<N; i++) cout << seq[i] << " ";
        cout << "\n";
        return ;
    }
    for(int num=idx; num<=6; num++){
        seq[cnt] = num;
        duplicateCombination(num, cnt+1);
    }
}

void permutation(int cnt){
    if(cnt == N){
        for(int i=0; i<N; i++) cout << seq[i] << " ";
        cout << "\n";
        return ;
    }
    for(int num=1; num<=6; num++){
        if(visited[num]) continue;
        visited[num] = true;
        seq[cnt] = num;
        permutation(cnt+1);
        visited[num] = false;
    }
}

void solve(){
    if(M==1) duplicatePermutation(0);
    else if(M==2) duplicateCombination(1, 0);
    else if(M==3) permutation(0);
}


int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    input();
    solve();
}