N과 M(1) 문제 풀이 - 자세한 주석 포함

15649번: N과 M (1)

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다.

https://www.acmicpc.net/problem/15649

15649번: N과 M (1)

/*
알고리즘을 한줄로 요약하면 이렇다.
    "1부터 N까지 고르기(이미 고른 것 제외하고)"를 길이 M이 될때까지 반복. M에 도달시 출력하고 리턴.

예를 들어 N=3, M=3인 경우.

1 > 11(x)
- > 12(o) > 121(x)
- - ----- > 122(x)
- - ----- > 123(o) - 출력
- > 13(o) > 131(x)
- - ----- > 132(o) - 출력
- - ----- > 133(x)
2 > 21(o) > 211(x)
- - ----- > 212(x)
- - ----- > 213(o) - 출력
- > 22(x) 
- > 23(o) > 231(o) - 출력
- - ----- > 232(x) 
- - ----- > 233(x)
3 > 31(o) > 311(x)
- - ----- > 312(o) - 출력
- - ----- > 313(x)
- > 32(o) > 321(o)
- - ----- > 322(x)
- - ----- > 323(x) - 출력
- > 33(x)


첫번째 수가 1인것만 좀더 자세히 보면

1(i=1){ i=1저장 go(lv=0) }   >> 11(i=1)(x) { continue }
                             >> 12(i=2)(o) { i=2저장, go(lv=1) }    >> 121(i=1)(x) 
                                                                 >> 122(i=2)(x) 
                                                                 >> 123(i=3)(o) - 출력
                             >> 13(i=3)(o) { i=3저장, go(lv=1) }    >> 131(i=1)(x)
                                                                 >> 132(i=2)(o) - 출력
                                                                 >> 133(i=3)(x)

-------------------------------------------------------------------

1. for(i = 1~N) 순회.(1부터 N까지 각각 고르는 경우)
2. 길이가 M이면(level == M) 숫자를 고르지말고 수열을 출력하고 리턴.
* 수열 출력 : numbers에 저장된 숫자 M개를 print.
3. Strat form level=0. (아무것도 고르지 않은상태)

---for문 내부---

<!> visited[i]=1 이면 i는 고려하지 않고 continue.
4. 선택하는 수 i 를 numbers[level]에 저장, visited[i] = 1
5. 다음에 오는 숫자 고르기 go(level+1)
6. go를 빠져 나온 수 i에 대하여 visited[i] = 0

-------------------------------------------------------------------*/

#include <iostream>

//문제에 주어진 값
int N, M;

//★현재까지 선택된 숫자를 저장할 배열 필요.
int selected[10];

//★중복된 수를 고르지 않기 위해, 골랐는지 안골랐는지를 표시할 배열 필요.
int visited[10]; 

using namespace std;

//몇번 째 수인지 확인할수 있는 변수 level만 전달해주면된다.
//다른 조건(N,M)은 전역변수로 나와있음.
void go(int level) {
    //레벨(=현재까지 고른수)이 끝이면...
    if (level == M) {
        //골라져있는거 출력하기
        for (int n = 0; n < level; n++) {
            cout << selected[n] << " ";
        }
        cout << "\n";
    }
    else {
        //다음 숫자 고르기(1부터N까지)
        for (int i = 1; i <= N; i++) {
            //숫자 i 고르기
            if (visited[i] != 1) {
                //현재 고른 수를 저장하고
                visited[i] = 1;
                selected[level] = i;
                go(level + 1); //go:재귀
                visited[i] = 0; //재귀에서 빠져나온 이후, 고른 것을 취소.

            }
        }
    }
    return;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N >> M;

    //길이 M개, 1~N
    //strat form level =0
    go(0);

    return 0;
}