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

15658 N과 M (9) 실버 2

문제 링크

문제

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

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

입력

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

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

출력

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

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

풀이

기존에 N과 M문제들을 풀었던 방식(queue와 vector를 사용)으로 해결하려 했으나, 메모리 초과와 시간초과에 걸렸다.

풀이를 찾아보다 기존 코드와 2가지 차이점이 있었는데

1. 중복수열이 나오는 조건을 찾아 제외
2. visited를 사용하는 재귀 사용

먼저 1번은 https://m.blog.naver.com/js568/221857286945 에서 힌트를 얻었다.

이전 수열의 마지막 항과 새로 추가할 값이 같으면 중복 수열이 된다!

먼저 {9,7,1,9}의 입력(N)이 있을 때, 사전 순으로 정렬하면 {1,7,9,9}

1
=> 1-7 (o)
=> 1-9 (o)
=> 1-9 (x)
7
=> 7-1 (o)
=> 7-9 (o)
=> 7-9 (x)
9
=> 9-1 (o)
=> 9-7 (o)
=> 9-9 (o)

1-9 이후 다음에 올 값인 4번 인덱스의 9는 이전 9와 같기 때문에 중복수열이 됨.

마찬가지로 7-9 다음 9가 같기 때문에 중복수열.

이 아이디어를 적용해 경우의 수를 줄일 수 있었다.

이후 visited를 사용해 재방문을 방지하고자 재귀를 사용하는 코드로 변경했다.

코드

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

int answer[9];
vector <int> ins;
int n, m;
bool visited[9] = { 0, };

void init()
{
    for(int i = 0; i < 8; i++)
    {
        visited[i] = 0;
    }
}

void promising(int size)
{
    if(size == m){
        for(int i = 0; i < m; i++)
        {
            cout << answer[i] << " ";
        }
        cout << "\n";
        return;
    }

    int prev_element = 0;

    for(int i = 0; i < n; i++)
    {
            if(prev_element != ins[i] && visited[i] == 0){
                answer[size] = ins[i];
                prev_element = ins[i];
                visited[i] = 1;
                promising(size+1);
                visited[i] = 0;
            }
    }
}

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

    for(int i = 1; i <= n; i++)
    {
        int in;
        cin >> in;
        ins.push_back(in);
    }
    sort(ins.begin(), ins.end());
    init();
    promising(0);
    
    return 0;
}

• ps
• back-tracking