[C++] 백준 5568 : 카드 놓기

백준 5568 : 카드 놓기

 

문제 링크:

www.acmicpc.net/problem/5568

5568번: 카드 놓기

 

 

문제 내용:

상근이는 카드 n(4 ≤ n ≤ 10)장을 바닥에 나란히 놓고 놀고있다. 각 카드에는 1이상 99이하의 정수가 적혀져 있다. 상근이는 이 카드 중에서 k(2 ≤ k ≤ 4)장을 선택하고, 가로로 나란히 정수를 만들기로 했다. 상근이가 만들 수 있는 정수는 모두 몇 가지일까?

예를 들어, 카드가 5장 있고, 카드에 쓰여 있는 수가 1, 2, 3, 13, 21라고 하자. 여기서 3장을 선택해서 정수를 만들려고 한다. 2, 1, 13을 순서대로 나열하면 정수 2113을 만들 수 있다. 또, 21, 1, 3을 순서대로 나열하면 2113을 만들 수 있다. 이렇게 한 정수를 만드는 조합이 여러 가지 일 수 있다.

n장의 카드에 적힌 숫자가 주어졌을 때, 그 중에서 k개를 선택해서 만들 수 있는 정수의 개수를 구하는 프로그램을 작성하시오.

 

 

Idea:

각 카드를 문자열로 입력받아 방문의 유무를 판단하여 카드를 선택할 수 있게 하였다.

 

아마, 백준 N과 M (1) 을 풀어봤다면 쉽게 접근할만한 문제였다.

 

 

Code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <set>
using namespace std;
 
char card[10][10];
char choice[4][10];
bool visit[10];
int n, k;
set<int> s;
 
int dfs(int cnt) {
    //k개를 선택했으면 문자열을 set에 저장
    if (cnt == k) {
        char str[20] = "\0";
        for (int i = 0; i < k; i++)
            strcat(str, choice[i]);
        s.insert(atoi(str));
    }
 
    //k개 선택하는 방법
    for (int i = 0; i < n; i++) {
        //방문하지 않은 곳이면
        if (!visit[i]) {
            visit[i] = true;//방문
            //문자열 이어 붙이기
            strcpy(choice[cnt], card[i]);
            //1추가해서 다음 dfs 돌리기
            dfs(cnt + 1);
            //dfs 탈출하면 방문기록을 false로
            visit[i] = false;
        }
    }
    return 0;
}
 
int main() {
    scanf("%d %d", &n, &k);
 
    for (int i = 0; i < n; i++) {
        scanf("%s", card[i]);
    }
    dfs(0);
    printf("%d\n", s.size());
    return 0;
}