백준 15563 N과M (9) C++ 풀이 (무조건 이해시켜드림)

안녕하세요~ 여러분~

프루니입니다^___^

 

오늘 풀어볼 문제는 백준 15663번 N과M (9) 문제입니다.

언어는 C++입니다~

 

N과M 시리즈가 주르륵 잘 풀려서 신났다가

이 문제에서 갑자기 막혀서 화가 났었어용 ㅎㅎ

 

중복되는 수열을 검사해야하는 조건을 구현하는 알고리즘을

고민하느라 굉장히 오래걸렸답니다 ㅜㅜ

만약 실전 코테였다면............으악으악으악!!!!!!!!!

 

코테 전에 풀어놔서 다행이에요ㅎㅎ!!!!!!!!!!!!!

 

자 그럼 문제 마스터하러 가주아~~!!!!!!!!!!!!!!!

 

---

문제

 

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

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

---

입력

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

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

---

출력

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

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

---

프루니의 풀이

사용 언어 : C++

사용 알고리즘 : 브루트포스

 

문제 해석 

1~N개의 숫자 중에 M개를 뽑아 나열하는 순열 문제입니다. 

이 문제는 모든 경우를 모두 출력해야하기 때문에 브루트포스를 사용해야 합니다.

 

여기서 중요한 것은 입력으로 주어지는 숫자가 중복될 수 있고 출력시에 중복되는 수열을 여러번 출력하면 안된다는 것이에요!

따라서 수열을 만들때 이미 존재하는 수열인지 검사해야해요!!

 

그런데 말이죵 -.-

 

수열이 중복되는 것을 검사하려면 수열의 숫자 하나하나를 비교해야하잖아요 ?

물론 해도 되지만 뭔가... 코드도 길어지고 .. 시간도 길어지고 ... 그래서 굉장히 찝찝하단 말이죵 ?

이부분에서 고민하다가 오래걸려서 빡쳤어요 ㅎㅎ.

 

자 지금 이 문제는 사전순으로 수열을 출력해야해요!

이 점을 이용하면 수열의 숫자를 하나하나 비교하지 않고도 수열 중복 검사를 할 수 있어요!!

(사전순일때만 가능한 방법이에요!! 문제에서 사전순 조건이 없으면 수열 하나하나 비교해서 중복검사하세요!!!!!!!)

 

어차피 사전 순 증가이기 때문에 구성된 수열의 마지막 요소만 다른지 비교해보면 됩니다!!

이게 무슨 말이냐면.

만약 5, 7, 3, 1중에 3개를 뽑아서 사전순으로 증가하는 수열을 구성한다고 생각해보세요

 

우리는 먼저 3개의 숫자를 뽑은 다음 사전순으로 증가하도록 나열하면 되겠죠?

 

자 그럼 (5, 7, 3)을 뽑든, (7, 5, 3)을 뽑든, (3, 5, 7)을 뽑든

사전순으로 증가하도록 나열하면 뭐가되죠 ?

예! 바로 3, 5, 7이 되겠죠!!!!!!!!!!!!!!

 

바로 이 사실을 이용하는 것이에요!

 

뽑는 순서에 관계없이 수열을 구성하는 숫자가 동일하면 어차피 순서는 정해져 있다는 말이에요!

따라서 우리가 해야하는 것은 순서를 나열하는 것이 아닌 뽑는것이에요!

어떻게 ?

직전 수열의 마지막 숫자와 다른 숫자를 뽑으면 됩니다!

 

만약 직전에 만든 수열이 3, 5, 7 이라고 해봅시다

마지막 숫자는 7이라는 것만 알고 있으면 됩니다!!

다음 수열을 만들기 위해 다시 첫번째 숫자를 뽑아야되겠죠 ? 

자 그럼 5, 7, 3, 1을 다시 돌면서 검사하는 거에요 

첫번째로 5는 직전 수열의 마지막 숫자인 7과 달라요

따라서 선택할거에요

두번째로 7은 직전 수열의 마지막 숫자인 7과 같아요!! 그러므로 지금 만들고 있는 수열에서는 선택하지 않아요!

그럼 두번째 숫자를 계속 찾아봐야겠죠? 

3은 직전 수열의 마지막 숫자인 7과 다르니까 선택할거에요.

그럼 이제 세번째 숫자만 선택하면 수열이 완성되겠죠?

1은 직전 수열의 마지막 숫자인 7과 다르니까 선택할거에요.

자 이렇게 한바퀴 돌아서 선택한 세개의 숫자는 바로 5, 3, 1 이에요~

이것을 사전순으로 증가하게 바꾸면 1, 3, 5에요~

 

이런식으로 모든 경우의 수를 돌면 구성만 다른 모든 조합을 뽑을 수 있어요!!

 

!여기서 잠깐! 호옥시 브루트포스에 대해 모르시는 분들이 있다면 보세용! (사실 제가 몰랐어용 히히)

 

브루트포스가 뭐죵?

브루트포스는 모든 경우를 하나도 빠짐없이 직접 다 실행하는 것이랍니다!

 

나무위키에 따르면

"브루트 포스(brute force), 키 전수조사(exhaustive key search) 또는 무차별 대입(無差別代入)은 조합 가능한 모든 문자열을 하나씩 대입해 보는 방식으로 암호를 해독하는 방법이다. 흔히 암호학에서 연구되나, 다른 알고리즘 분야에서도 사용되고 있다." 라고 합니다!

 

모든 경우를 다 돌아봐야 하는 문제라면 브루트포스 알고리즘을 쓰면 되겠어용!

 

그럼 코드로 바로 가볼게요!!

설명은 주석으로!!!

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
#define MAX 9

int N, M;
vector<int> numbers; // 입력받은 N개의 숫자를 담고 있는 벡터입니다
bool visited[MAX]; // N개의 숫자가 뽑힌 적이 있는지 여부를 담고 있는 배열입니다
int sequence[MAX]; // 뽑은 숫자를 저장하는 배열입니다


//재귀함수
//매개변수 cnt는 현재 뽑아야하는 숫자의 순번이에요! 
//이미 2개를 뽑았고 3번째 숫자를 뽑을 차례라면 cnt에 3을 넣어 함수를 호출하면 됩니다!
void DFS(int cnt)
{
    //재귀함수 탈출조건 : m개 다 뽑을 때 출력 후 return
    if (cnt == M)
    {
        for (int i = 0; i < M; ++i)
        {
            cout << sequence[i] << ' ';
        }
        cout << '\n';
        return;
    }

    int preArrLast = 0; // 직전에 완성된 배열의 마지막 요소를 저장하는 변수입니다!

    //N개의 숫자를 모두 돌며 검사하여 추가하거나 추가하지 않는 반복문입니다~
    for (int i = 1; i <= N; ++i)
    {
        if (!visited[i] && preArrLast != numbers[i]) // 뽑은적이 없고 직전 배열의 마지막 요소와 다른 숫자이면 뽑아요!(이전에 뽑힌 수열인지 검사하는과정이에요!)
        {
            sequence[cnt] = numbers[i]; // 현재 뽑고있는 순서의 숫자로 numbers의 i번째 요소를 추가해요!
            visited[i] = true; // numbers의 i번째 요소를 뽑았기 때문에 뽑았다는 표시로 visited의 i번째 요소를 true로 설정해요~
            preArrLast = numbers[i]; // 다음 배열을 구성할때 중복검사를 하기 위해 현재 뽑은 숫자를 preArrLast에 저장해요!
            DFS(cnt + 1); // M개의 숫자 중에서 cnt번째 숫자까지 뽑았으니까 그다음 숫자인 cnt+1번째 숫자를 뽑기위해 cnt+1을 매개변수로 DFS함수를 호출해요
            visited[i] = false; // 바로 위 코드인 DFS함수가 한번 끝나고 돌아왔기 때문에 그다음 M개의 숫자를 새로 뽑기전에 뽑았던 기록을 모두 false로 초기화해요!
        }
    }
}

int main()
{
    cin >> N >> M; // N, M을 입력받아요~

    int num = 0;
    numbers.push_back(num);
    for (int i = 1; i <= N; ++i) // N개의 숫자를 입력받고 numbers에 저장해요~
    {
        cin >> num;
        numbers.push_back(num);
    }

    sort(numbers.begin(), numbers.end()); // 문제에서 출력할때 사전 순서로 출력해야한다는 조건이 있기때문에 입력받은 숫자를 미리 오름차순으로 정렬해놔요~
    
    DFS(0); // 재귀함수 시작!
    return 0;
}

 

후 여러분 고생많으셨어요~

이해가 되셨다면 공감버튼 한번씩 눌러주세요(꾸벅)

이해가 안되셨다면 댓글로 질문해주세요!!! 바아로 갑니다.

 

될때까지 하면 됩니다.

반드시 뿌십시다!!

 

자 그럼 저는 또 다음 문제를 가지고 올게요~ 

안녕~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~