[ 백준 BOJ / c++ ] 15663번 N과 M (9)

🤔 문제

 

링크 : https://www.acmicpc.net/problem/15663

 

---

👀 접근 방식

모든 경우의 조합을 생각하되, 오름차순 정렬 및 중복 출력X 를 고려해야 한다. 조합 및 순열을 만드는 방법으로는 "백트래킹"을 사용하도록 한다.  

 

"오름차순 정렬"의 경우 백트래킹을 진행하기 전 입력값을 오름차순으로 정렬 후 진행하면 낮은 값 ~ 높은 값 순으로 출력이 되기 때문에 함수 실행 전 sort함수를 사용해 미리 오름차순 정렬을 진행한다.

 

"중복 출력 방지"의 경우 다음 입력값을 최근 조합의 마지막 값과 같은지 검사해, 같지 않을 경우 다음 백트래킹을 진행하면 된다. 예를 들어, 이전 조합의 "2 4" 이고 다음 숫자가 4인 경우 조합 "2 4"의 마지막 값인 4와 같기 때문에 다음 숫자 4에 대해 백트래킹을 진행하지 않으면 된다. 

---

💻 코드

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

using namespace std;

int n, m;
int input[8];
int ans[8];
bool isUsed[8];

void func(int index)
{
    // 현재 위치가 m 과 같을시 정답 출력
    if (index == m)
    {
        for (int i = 0; i < m; ++i)
            cout << ans[i] << " ";
        cout << '\n';

        return;
    }

    // 이전 값을 저장할 변수 선언
    int preValue = 0;


    for (int i = 0; i < n; ++i)
    {
        // 사용할 수 있고 이전값이 현재 값과 다를 경우 실행
        if (!isUsed[i] && preValue != input[i])
        {
            //정답에 추가
            ans[index] = input[i];
            
            //현재값을 저장
            preValue = input[i];

            // 현재 번호를 사용중으로 번경
            isUsed[i] = true;

            //깊이를 1칸 늘려 재귀 함수 실행
            func(index + 1);

            // 현재 번호를 사용 끝으로 번경
            isUsed[i] = false;
        }
    }

}

int main() {

    // 출력이 많아질 수 있으니 동기화 해제
    ios_base::sync_with_stdio(0);
    cout.tie(0);

    // n,m 그리고 숫자들 입력 받음
    cin >> n >> m;

    for (int i = 0; i < n; ++i) cin >> input[i];

    // 오름차순 정렬
    sort(input, input + n);

    // 깊이 0 부터 시작
    func(0);

    return 0;
}