BOJ 15649. N과 M (1)

• 문제링크 : https://www.acmicpc.net/problem/15649

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
입력 : 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

1. 문제 해석

N=5, M=3 이면, 3개의 수를 고르는데, 1,2,3,4,5 중에 하나를 고른다.
5가지, 4가지, 3가지 이다. (5x4x3 = 60가지)

1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
...

_ _ _
↑ ↑ ↑
5   4  3(1부터 5중에서 사용하지 않은 수)
항상 N, N-1, ... , 1부터 N중에서 사용하지 않은 수 가 오게 된다.

시간 복잡도

N=8, M=8 이면, 8! = 40,320 이므로 브루트 포스로 충분히 풀 수 있는 경우의 수이다.
(n!의 시간복잡도는 1만 차이나도 매우 큰 차이를 보이므로 범위를 잘 고려해야 한다.)

2. 문제 풀이

중복 없는 수열을 모두 출력하기 위해서 check배열이 하나 필요하다. 여기에서 체크를 걸고, 재귀호출하고, 다시 체크를 풀어줌으로써 중복을 피하면서 수열을 출력할 수 있다. 우선, 재귀 함수를 설계하기 위해서 탈출 조건과 반복 실행할 부분을 나누어서 생각해본다.

1) 탈출 조건 : count 값이 M이 되었을때 하나의 수열을 출력
2) 반복 실행 : go(cnt+1)로 자릿수 증가

M과N은 초반에 입력받고 변하지 않으므로 그냥 전역변수로 선언하였다. cnt값만 매개변수로 선언해서 탈출 조건에 걸리도록 한다.

#include <iostream>
using namespace std;

int N, M, n[10];
bool ch[10];

void go(int cnt){
    if(cnt==M){	// 탈출 조건문
        for(int i=0;i<M-1;i++)
            cout << n[i] << ' ';
        cout << n[M-1] << '\n';
        return;                
    }
    else{	// 반복 실행문
        for(int i=1; i<=N; i++){
            if(ch[i]) continue;
            ch[i] = true; n[cnt]=i; // check걸고, n배열에 선택된 수 추가 
            go(cnt+1);		    // 다음 숫자 넣어보고 
            ch[i] = false;	    // check풀고, n배열에 선택된 수 제거할 필요x 
        }
    }
}
int main(){
    cin >> N >> M;
    go(0);
    return 0;
}

• Point 1.  cout << endl 을 해서 시간초과가 났다. 그냥 cout << '\n'을 사용해야겠다.
• Point 2.  check배열만으로 문제를 풀려고 했는데, cnt값이 0부터 시작하면 ch[0]에 1이 들어가 버리는 문제가 있고, false로 풀어주기 때문에 계속 1,2만 출력된다. 따라서 별도의 n배열에 수열을 저장해 놓아야한다.
• Point 3.  ch[i] = false를 하면서 n[cnt]=0을 하지 않는 것은 어차피 다시 n[cnt]=i에서 덮어써져서 굳이 그럴 필요가 없기 때문이다.

재귀함수에 매개변수로 N,M을 포함

#include <iostream>
using namespace std;
bool c[10];
int a[10];
void go(int index, int n, int m) {
    if (index == m) {
        for (int i=0; i<m; i++) {
            cout << a[i];
            if (i != m-1) cout << ' ';
        }
        cout << '\n';
        return;
    }
    for (int i=1; i<=n; i++) {
        if (c[i]) continue;
        c[i] = true;
        a[index] = i;
        go(index+1, n, m);
        c[i] = false;
    }
}
int main() {
    int n, m;
    cin >> n >> m;
    go(0,n,m);
    return 0;
}

---

BOJ 15650. N과 M (2)

• 문제링크 : https://www.acmicpc.net/submit/15650

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
• 고른 수열은 오름차순이어야 한다.

입력 : 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

1. 문제 해석

N=5, M=3이면
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
...
이렇게 수열이 만들어지는데, 오름차순이어야 하므로 뒤에 올 수는 앞의 수보다 무조건 커야한다.

2. 문제 풀이

N과 M (1)을 이용한 방법

i _ _
↑ ↑ ↑
5 ( i+1부터 5까지 중에서 사용하지 않은 수 )
항상 N, N-1, ... , i+1부터 N까지 중에서 사용하지 않은 수 가 오게 된다.

#include <iostream>
using namespace std;
// bool c[10];
int a[10];
void go(int index, int start, int n, int m) {
    if (index == m) {
        for (int i=0; i<m; i++) {
            cout << a[i];
            if (i != m-1) cout << ' ';
        }
        cout << '\n';
        return;
    }
    for (int i=start; i<=n; i++) {
        // if (c[i]) continue;
        // c[i] = true;
        a[index] = i;
        go(index+1, i+1, n, m);
        // c[i] = false;
    }
}
int main() {
    int n, m;
    cin >> n >> m;
    go(0,1,n,m);
    return 0;
}

N과 M (1)의 풀이에서 start라는 매개변수가 추가되었다. start에 i+1을 넣어서 재귀호출 함으로써 앞의 수 보다 큰 수만 a배열에 저장하도록 하였다. 어차피 큰 수만 저장하므로 당연히 중복이 되지 않는다. 따라서 c배열로 체크하는 부분은 빼도 무방하다.

선택하거나 하지않는 경우를 고려한 방법

1 2 3 을 가지고 만들 수 있는 수열에서
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1 은 오름차순이 아니므로 모두 의미가 없다. 1 2 3 하나만 가능한 것이다.

따라서 1 부터 N까지의 수를 선택하거나(o) 선택하지 않는(x)다는 관점에서 문제를 해석할 수도 있다. 즉, M개의 자리에 어떤 수 가 들어갈지 결정하는 것이다.
1 2 3 4 5 ... (N-1) N
o o o o o ... o o
x x x x x ... x x
2 2 2 2 2 ... 2 2 각각 2가지 경우를 모두 곱하면 총 시간복잡도는 O(2^N)이 된다.

기존의 방식을 이용하면 N개의 수 중에서 M개를 고르는 경우의수가 실행되므로, Nx(N-1)x ...을 총 M번 반복한다. 이는 N,M이 매우 클 때 O(N!)로 수렴한다. 하지만 이 방법으로 O(2^N)의 시간복잡도를 가지게 되어 시간을 획기적으로 줄일 수 있다.

#include <iostream>
using namespace std;
int a[10];
void go(int index, int selected, int n, int m) {
    if (selected == m) { // 선택한 수가 M개일 때 출력 후 종료 (정답을 찾은 경우)
        for (int i=0; i<m; i++) 
            cout << a[i] << ' ';        
        cout << '\n';
        return;
    }
    if (index > n) return;	// 모두 다 x인 경우 종료 (불가능한 경우)
    a[selected] = index;	// index를 결과에 추가 o
    go(index+1, selected+1, n, m);
    a[selected] = 0;		// index를 결과에 추가 x
    go(index+1, selected, n, m);
}
int main() {
    int n, m;
    cin >> n >> m;
    go(1, 0, n, m);
    return 0;
}

여기서 주의할 점은 오름차순으로 출력해야하므로 재귀호출을 할 때에도 index를 결과에 추가하는 부분을 먼저 호출했다는 것이다.

---

BOJ 15651. N과 M (3)

• 문제링크 : https://www.acmicpc.net/problem/15651

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

1부터 N까지 자연수 중에서 M개를 고른 수열
같은 수를 여러 번 골라도 된다.

입력: 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 7)

1. 문제 해석

이 문제는 앞의 문제와 달리 중복 선택이 가능하다.

N=5, M=3이면
1 1 1
1 1 2
1 1 3
1 1 4
1 1 5
1 2 1
...
이렇게 수열이 만들어지는데, 코드 상에서는 N과 M (1)에서 if(c[i]) continue; 이 부분만 빼주면 된다. 저 부분이 중복을 제거하는 부분이기 때문이다.

2. 문제 풀이

#include <iostream>
using namespace std;
bool c[10];
int a[10];
void go(int index, int n, int m) {
    if (index == m) {
        for (int i=0; i<m; i++) {
            cout << a[i];
            if (i != m-1) cout << ' ';
        }
        cout << '\n';
        return;
    }
    for (int i=1; i<=n; i++) {
        //if (c[i]) continue;
        c[i] = true;
        a[index] = i;
        go(index+1, n, m);
        c[i] = false;
    }
}
int main() {
    int n, m;
    cin >> n >> m;
    go(0,n,m);
    return 0;
}

---

BOJ 15652. N과 M (4)

• 문제링크 : https://www.acmicpc.net/problem/15652

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

1부터 N까지 자연수 중에서 M개를 고른 수열
같은 수를 여러 번 골라도 된다.
고른 수열은 비내림차순이어야 한다.
길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.
입력 : 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

1. 문제 해석

비내림차순이라는 말은 같거나 오름차순이면 된다는 말과 같다. 따라서 N과 M (2)에서 비내림차순 조건만 추가되었으므로, 'start+1(선택하거나) start(하지않거나)' 로 처리했던 부분을 그냥 start로 처리하면 된다. N과 M (1)에서 start라는 매개변수만 추가된 형태이기도 하다.
(1 1 2 2 3 <- 이런식으로 수열을 만드는 것도 허용)

물론, N과 M (2) 에서의 선택하거나 선택하지않는 방법으로도 풀이가 가능하다. 하지만 이 문제에서는 그렇게 효율적이지 못한 방법이다.

1 2 3 4 5 ... (N-1) N
o o o o o ... o o
x x x x x ... x x

여기서 1을 선택하여 포함한다면, 몇개를 선택하는가? 라는 조건이 추가된다. 따라서 선택하는 경우를 2가지가 아닌 i개를 선택하는 경우로 세분화해야 한다.

2. 문제 풀이

index+1번째에 start부터 저장

#include <iostream>
using namespace std;
bool c[10];
int a[10];
void go(int index, int start, int n, int m) {
    if (index == m) {
        for (int i=0; i<m; i++) {
            cout << a[i];
            if (i != m-1) cout << ' ';
        }
        cout << '\n';
        return;
    }
    for (int i=start; i<=n; i++) {
        // c[i] = true;
        a[index] = i;
        go(index+1, i, n, m);
        // c[i] = false;
    }
}
int main() {
    int n, m;
    cin >> n >> m;
    go(0,1,n,m);
    return 0;
}

선택하는 방식으로 구현

#include <iostream>
using namespace std;
int cnt[10];
void go(int index, int selected, int n, int m) {
    if (selected == m) {
        for (int i=1; i<=n; i++) {
            for (int j=1; j<=cnt[i]; j++) {
                cout << i << ' ';
            }
        }
        cout << '\n';
        return;
    }
    if (index > n) return;
    for (int i=m-selected; i>=1; i--) {
        cnt[index] = i;
        go(index+1, selected+i, n, m);
    }
    cnt[index] = 0;
    go(index+1, selected, n, m);
}
int main() {
    int n, m;
    cin >> n >> m;
    go(1, 0, n, m);
    return 0;
}