[5일차] 조합론 E - 5568: 카드 놓기

실버 Ⅴ

 

#include <iostream>
#include <set>
#define MAXN 10

using namespace std;

int n, k;
int Top;
int cards[MAXN];
bool Visit[MAXN];
int D[MAXN];

set<int> s;

void backtracking() {
    if (Top == k) {
        //만들어진 숫자 SET에 넣기
        int tmp = 0;
        for (int i = 0; i < k; i++) {

            //printf(" --> %d ", cards[D[i] - 1]);
            //자기 길이만큼 원래 있던거 밀어줌
            int tens = cards[D[i] - 1];
            do {
                tmp *= 10;
            } while (tens /= 10);

            //자기 더해줌
            tmp += cards[D[i] - 1];
            //printf("\ntmp: %d\n", tmp);
        }
        //printf("\n");
        s.insert(tmp);
        //printf("%d 넣음\n", tmp);
        return;
    }

    for (int i = 1; i <= n; i++)  {
        if (!Visit[i]) {
            Visit[i] = true;
            D[Top++] = i;
            backtracking();
            Top--;
            Visit[i] = false;
        }
    }
}
int main() {
    scanf("%d%d", &n, &k);

    for (int i = 0; i < n; i++) {
        scanf("%d", &cards[i]);
    }

    Top = 0;
    backtracking();
    printf("%d", s.size());
    return 0;
}

 

조합론 문제

 

강사님이 올려주신 순열 소스를

그래도 가져다가 썼다

top이랑.. 뭐 뜻하는지도 모르는데

아이고~

 

근데 좀 이상하게 푼거같기도하고..

괜찮나?

강사님이 푸는 방법은 아래 첨부

비교비교

 

//순열 응용
#include <bits/stdc++.h>

using namespace std;

#define MAXN 10

int Card[MAXN];
bool Visit[MAXN];
set<string> S;
int N, K;

void backtracking(int index, string numStr)
{
    if(index == K)
    {
        S.insert(numStr);
        return ;
    }

    for(int i=0; i<N; i++)
    {
        if(Visit[i]==false)
        {
            Visit[i]=true;
            backtracking(index+1, numStr + to_string(Card[i]));
            Visit[i]=false;
        }
    }
}

int main()
{
    scanf("%d %d", &N, &K);

    for(int i=0; i<N; i++) scanf("%d", &Card[i]);

    backtracking(0, "");//index, numStr

    printf("%d", (int)S.size());

    return 0;
}