[백준] 15663번 N과 M(9) (C++)

 

목차

0. 서론

1. 문제 방향

2. 코드

 

0. 서론

제한시간 1초

메모리 512MB

---

문제

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

• N개의 자연수 중에서 M개를 고른 수열

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.

출력

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

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

---

까지가 문제다. 필자가 푸는 시점에서는 실버2였다.

역시 N과 M 시리즈는, 골드 이후의 문제를 푸는데에 큰 발돋움이 되는 문제들이 많다.

이 문제 또한 그랬다.

 

1. 문제방향

필자의 생각 흐름이 궁금하지 않고, 문제 푸는 방법이 궁금하다면 아래의 꺾어진 구분선 아래부터 보면 된다.

 

처음에 이 문제를 접근할 때, "중복되고 연속되지 않은 수"가 주어지면서 "수열이 중복되지 않아야 한다"가 어떻게 풀어야 할 지 감이 안잡혔다. 우선 N과 M은 8보다 작기에 수가 그리 크지 않기에, 각 자리별로 개수를 멕이고 분배할려 했더니 그럼 출력을 모두 기록하고 확인해야만 동일한 출력인지 아닌지 알 수 있을 듯 했다.

---

그럼 dfs처럼 재귀를 사용하여 출력을 걸 때, 중복되는 숫자를 어떻게 제거할 수 있을지 생각해 보았다.

 

우선, 기본적으로 출력이 "증가하는 사전 순"이기 때문에, 입력받은 테이블은 모두 sort를 해줘야 한다.

 

겹치는 경우 1)

 

만일 M이 2이고, 위와 같이 테이블이 주어졌다고 했을 때, 첫 번째 재귀에서 첫 번째 숫자인 1을 고른 후, 다음 재귀로 넘어간다면

처럼 [1 9]가 겹치게 된다.

 

 

겹치는 경우 2)

네 번째인 9를 잡았을 때, 

 

"본인"인 9는 넘겼지만, "본인 다음"에 해당하는 같은 수 9를 또다시 짚는 경우는 [9 9]가 중복해서 발생하게 된다.

그리고, 여기서 만약 [9 9]를 한번만 출력하게 했다고 가정해보면, 다음의 겹치는 경우3에서 또 겹칠 수 있게된다.

 

겹치는 경우 3)

 

앞서서 [9 9]를 print 했지만, 다섯 번째의 9를 짚게 되면, 앞서 출력한 [9 9]가 또 출력되게 되는 경우가 발생할 수 있다.

 

해결

코드를 보고싶은 사람은 그냥 다음 index로 넘어가면 된다. 해당 페이지에서는 구조적인 내용을 다룬다.

우선, [1 1]과 같이 중복되는 경우는

vector<int> stack;
vector<bool> visited;

void logic(int depth) {
	for(int i = 0; i < (int)depth.size(); ++i) {
    	if(!visited[i]) {
        	visited[i] = true;
            logic(depth + 1);
            visited[i] = false;
        }
    }
}

 

이런 dfs의 기본 visited구조로 피할 수 있고,

 

겹치는 경우 1,2,3을 모두 타개할 수 있는 방법이 하나 있다.

겹치기 직전과 겹친 후의 동작들을 하나하나 보고있자면,

"전에 선택한 선택을 다시 선택하지 않게"하는 것 하나만으로 이를 해결할 수 있다.

 

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N,M;
vector<int> table;
vector<int> stack;
vector<bool> visited;

void init() {
    int temp;
    cin >> N >> M;

    visited.resize(N, false);

    for(int i = 0; i < N; ++i) {
        cin >> temp;
        table.push_back(temp);
    }
    sort(table.begin(), table.end());
}

이렇게 입력을 받아준 후,

 

void logic(int depth) {
    if(depth >= M) {
        return;
    }

    int bef = 0;

    for(int i = 0; i < (int)table.size(); ++i) {
        if(!visited[i] && table[i] != bef) {
            bef = table[i];
            
            visited[i] = true;
            stack.push_back(table[i]);
            
            logic(depth+1);
            
            visited[i] = false;
            stack.pop_back();
        }
    }
}

이런 형식으로 짜 내려가면 된다.

 

물론 보기 쉽게 하느라 print 하는 부분을 제외했고, if return 부분에 print하는 로직을 넣어주면 된다.

 

 

2. 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N,M;
vector<int> table;
vector<int> stack;
vector<bool> visited;

void init() {
    int temp;
    cin >> N >> M;

    visited.resize(N, false);

    for(int i = 0; i < N; ++i) {
        cin >> temp;
        table.push_back(temp);
    }
    sort(table.begin(), table.end());
}

void logic(int depth) {
    if(depth >= M) {
        for(int i = 0; i < (int)stack.size(); ++i) {
            cout << stack[i] << " ";
        }
        cout << '\n';
        return;
    }

    int bef = 0;

    for(int i = 0; i < (int)table.size(); ++i) {
        if(!visited[i] && table[i] != bef) {
            bef = table[i];
            visited[i] = true;
            stack.push_back(table[i]);
            logic(depth+1);
            visited[i] = false;
            stack.pop_back();
        }
    }
}



int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    init();
    logic(0);

    return 0;
}

 

입출력 가속의 경우 4ms가 더 빠르다.