[백준] 15663. N과 M(9)

 

 

N과 M문제 중에 이 문제만 정답률이 47%로 낮다.

낮은 이유가 있었다.

중복되는 것에 대해서 트릭이 필요했다.

두 가지 방법을 소개한다.

수열 인덱스를 골라 나갈 것인데

예를 들어 4개중 2개를 골라보자.

4 2

9 7 9 1

2번 예제이다.

0 1
0 2
0 3
1 0
1 2
1 3
2 0
2 1
2 3
3 0
3 1
3 2

이 될것이다.

우선 v에 입력을 순서대로 저장하면 1 7 9 9 가 될 것인데,

저 순서대로 출력한다면,

1 7
1 9
1 9
7 1
7 9
7 9
9 1
9 7
9 9
9 1
9 7
9 9

이렇게 될 것이다.

중복되는 수열이 많다. 이것을 제거하는 방법은 해당 depth에서 새로운 인덱스를 고르기전에(for문전에)

이전 값을 기억하는 변수를 만드는 것이다.(before)

따라서, 해당 depth에서 for문을 돌다가 바로 이전에 변수를 선택했다면, 패스하게 만들면 된다.

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int N, M;
vector<int> v;
bool chk[8];
int nums[8];

void dfs(int depth){
    if (depth == M){
        for (int i=0; i<M; ++i) printf("%d ", nums[i]);
        puts("");
        return;
    }
    int before = -1;
    for (int i=0; i<v.size(); ++i){
        if (!chk[i] && (i == 0 || before != v[i])) {
            before = v[i];
            nums[depth] = v[i];
            chk[i] = true;
            dfs(depth + 1);
            chk[i] = false;
        }
    }
}

int main() {
    scanf("%d %d", &N, &M);
    int val;
    for (int i=0; i<N; ++i) {
        scanf("%d", &val);
        v.push_back(val);
    }
    sort(v.begin(), v.end());
    dfs(0);

    return 0;
}

 

밑에는,

숫자값이 1<= n <= 10,000이라는 점에서 착안해, 인덱스값에서 bool을 반환하는 배열을 만들어

이전 숫자를 기억하는 방법이다. 그런데 우리는 v가 이미 정렬되고 1 2 7 9 9 9 9 이런식으로 나오므로 굳이 이렇게 할필요는 없다. 그래도 좋은 아이디어 인 것 같아서 첨부한다.

 

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int N, M;
vector<int> v;
bool chk[8];
int nums[8];

void dfs(int depth){
    if (depth == M){
        for (int i=0; i<M; ++i) printf("%d ", nums[i]);
        puts("");
        return;
    }
    bool used[10001] {false};
    for (int i=0; i<v.size(); ++i){
        if (used[v[i]] || chk[i]) continue;
        used[v[i]] = true;
        nums[depth] = v[i];
        chk[i] = true;
        dfs(depth + 1);
        chk[i] = false;
    }
}

int main() {
    scanf("%d %d", &N, &M);
    int val;
    for (int i=0; i<N; ++i) {
        scanf("%d", &val);
        v.push_back(val);
    }
    sort(v.begin(), v.end());
    dfs(0);

    return 0;
}

 

 

[참고 - https://www.acmicpc.net/source/13138416]

[참고 - https://m.blog.naver.com/PostView.nhn?blogId=pyl970&logNo=221512805995&proxyReferer=https%3A%2F%2Fwww.google.com%2F]