[C++] Boj 15657 N과 M (8)

문제 링크

N과 M (8)

 

N과 M 시리즈를 풀면서 뭔가 계속 날먹하고 있는 기분이다...

큰 틀은 똑같고 부분부분 조건만 바꿔주면 되는 문제이다 보니...

약간 공부를 안 하는(?) 느낌이다.

아무튼 점수 올리고 개꿀. ㅎㅎ

 

문제 해석

N개의 자연수 중 M개를 뽑는다. 이때 수는 중복으로 뽑아도 되지만 다른 수열과 순서는 같으면 안된다. 또한 내림차순 수열은 불가능하다.

 

접근

백트래킹을 이용하여 풀었다.

이때 중복은 허용하고, 내림차순 수열을 방지하기 위해 조건을 하나 붙였다.

아까 뽑았던 숫자가 지금 뽑을 숫자보다 크면, 이 수열은 내림차순 수열이 되므로 pass 한다.

 

코드

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

// N개 중에서, M개 뽑음
int N, M;

// n번째로 뽑은 수를 저장
int picked[10];

// 숫자 모음
int numbers[10];

// k 번째로 저장할 수를 탐색 
void Solve(int k)
{
    if (k == M)
    {
        for (int i = 0; i < M; i++)
            cout << picked[i] << ' ';
        cout << '\n';
        return;
    }

    for (int i = 0; i < N; i++)
    {
        if (k > 0 && picked[k - 1] > numbers[i]) continue;
        picked[k] = numbers[i];
        Solve(k + 1);
    }
}

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

    cin >> N >> M;
    for (int i = 0; i < N; i++)
        cin >> numbers[i];
   
    // 사전순으로 찾기 위해 배열을 정렬
    sort(numbers, numbers + N);

    Solve(0);

    return 0;
}