8129 몇 번째 조합 (정올)

문제 풀이 과정

 

백준 N과 M과 굉장히 문제가 유사하지만 그건 순열문제, 이건 조합문제로 visited[i]제거하고 N과 K가 가능한 조합을 모두 만든 다음, 

만약 A가 N과 K로 만든 조합안에 들어있다면 그걸 문제에서 요구하는 인덱스데로 출력시킨다.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> pc;
vector<string> s;
int n, k;
vector<vector<int>> combi;

void comb(int s, int d){

    if (d == k){
        combi.push_back(pc);
        return;        
    }

    for (int i = s; i <= n; i++){
        pc.push_back(i);
        comb(i + 1, d + 1);
        pc.pop_back();
    }    
}

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

    comb(1, 0);

    sort(combi.begin(), combi.end());

    vector<int> target(k);

    for (int i = 0; i < k; i++){
        cin >> target[i];
    }
    
    auto idx = find(combi.begin(), combi.end(), target); //중요(아이디어 안떠올랐음 여기서)

    if (idx == combi.end()){
        cout << "None" << '\n';
    } else{
        cout << distance(combi.begin(), idx) + 1 << '\n';
    }

    return 0;
}

 

- 조합을 만드는 부분에서 만약 뽑아낸 수들이 K와 같아진다면 2차원 벡터에 1 2 3 의 형태로 더해주는 부분 생각에서 조금 막혔었음.

- 그리고 만약 1 3 5 가 combi 2차원 벡터안에 들어있다면 그 인덱스를 출력하라 및 인덱스 구하는 과정을 잘 생각해야함.