[백준] 15665번: N과 M (11) C++로 풀어보기

15665번 설명

생각

앞선 N과 M 문제처럼 백트래킹을 사용하면 된다.

 

백트래킹(backtracking)이란? : 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법을 말합니다. 최적화 문제와 결정 문제를 푸는 방법이 됩니다.

출처 : https://chanhuiseok.github.io/posts/algo-23/

알고리즘 - 백트래킹(Backtracking)의 정의 및 예시문제

 

만약 백트래킹에 대해서 더 자세히 배우고 싶다면 바킹독님의 강의를 듣는 것을 추천한다.

바킹독 백트래킹 강의

 

 

다른 점은 같은 수를 여러 번 골라도 된다는 점이다.

그렇다면 수가 사용되었는 지 검사하는 부분은 빼도 된다.

 

그리고 예제 입력 1을 보면 두 번째 줄에 '4 4 2' 이렇게 입력되었는데, 4가 두 개가 있어서 출력에 문제가 생긴다.

이 문제를 풀 때 벡터를 이용할 예정인데, 벡터에서 중복된 수를 지우는 방법을 찾아봐야겠다. 

 

코드

#include <bits/stdc++.h>
using namespace std;

int n, m;
vector <int> v;
int arr[10];

void func(int k) { // 현재 k개까지 수를 택했음.
    if (k == m) { // m개를 모두 택했으면
        for (int i = 0; i < m; i++)
            cout << arr[i] << ' '; // arr에 기록해둔 수를 출력
        cout << '\n';
        return;
    }

    for (auto it = v.begin(); it != v.end(); it++) { // 백트래킹을 사용한다.
        arr[k] = *it; // 배열에 현재 iterator가 가리키는 수를 넣는다. 
        func(k + 1);  // 한 단계 더 들어간다.
    }
}

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    
    while (n--) { // 수를 입력받아 벡터에 넣는다.
        int x;
        cin >> x;
        v.push_back(x);
    }
    
    sort(v.begin(), v.end()); // 오름차순으로 정렬
    v.erase(unique(v.begin(), v.end()), v.end()); // 중복된 수 제거

    func(0); // func(0) 실행
}

일단 벡터 안에 입력된 중복된 수를 없애려면 sort를 이용하여 정렬을 하고 unique와 erase를 이용해서 중복된 수를 삭제를 하면 된다.

(밑에 링크를 참고하면 더 자세히 알 수 있다.)

https://kkaeruk.tistory.com/19

[C++ STL : vector] 벡터 중복원소 제거

 

 

결과

15665번 결과