백준 N과 M (1) [c++]

15649 N과 M (1) 실버1

문제

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

1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

입력

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

출력

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

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

풀이

• 모든 가능한 경우를 찾아야 하므로 dp보다는 백트레킹이 적절해보임.
• queue와 promising함수를 만들어 설계.
• queue에 배열(편의상 vector 사용)을 집어넣고 하나씩 꺼내 promising함수에 하나씩 집어넣음. (큐가 빌때까지.)
• promising함수에서는 1~N까지 확인해 배열에 일치하는 값이 있는지 확인하고 없다면 그 값을 추가한 새 배열을 큐에 삽입.(1~N까지 중 없는 것을 모두 큐에 삽입)

• 그 전에 promising함수에서 배열의 사이즈가 m이면(모두 추가했다면) 출력.

• 첫 시도에 시간초과가 떴다.
  • 코드를 확인해보니 최종적으롤 3중반복문이긴하나 n과 m이 최대 8이므로 시간초과가 난 이유가 없어 보인다.(실제 평균적으로 8보다 작게 돌아감)
  • 찾아보니 이놈이 문제였음.
  • c++에서 endl은 \n과는 다르게 flush()함수를 겸하기 때문에 실행시간이 오래걸린다 한다.
  • endl > \n > printf 순으로 빠르다고 한다. (new info)

cout << i << endl : 4874ms
cout << "i" << "\n" : 1399ms
printf("%d\n", i) : 295ms

코드

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

queue <vector<int> > q;
int n, m;

void promising(vector<int> v)
{
    int size = v.size();

    if(size == m){
        //print & return;
        for(int i = 0; i < m; i++)
        {
            cout << v[i] << " ";
        }
        cout << "\n";
        return;
    }

    for(int i = 1; i <= n; i++)
    {
        int varified = 1;
        for(int s = 0; s < size; s++){
            if(v[s] == i){
                varified = 0;
            }
        }
        if(varified == 1){
            vector<int> add(v);
            add.push_back(i);
            q.push(add);
        }
    }
}

int main(){
    cin >> n >> m;

    for(int i = 1; i <= n; i++)
    {
        vector<int> v;
        v.push_back(i);
        q.push(v);
    }

    while(!q.empty()){
        int qsize = q.size();
        //cout << "q_size : " << qsize << endl;
        for(int i = 0; i < qsize; i++)
        {
            vector<int> t = q.front();
            q.pop();
            promising(t);

        }
    }
    
    return 0;
}

총평

• endl이 시간을 많이 잡아먹는다는걸 새로 알게 됨.

• ps
• back-tracking