[BOJ 백준] 카드놓기(5568) C++

 

링크 : https://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개를 선택해서 만들 수 있는 정수의 개수를 구하는 프로그램을 작성하시오.

 

입력 : 

첫째 줄에 n이, 둘째 줄에 k가 주어진다. 셋째 줄부터 n개 줄에는 카드에 적혀있는 수가 주어진다.

 

출력 : 

첫째 줄에 상근이가 만들 수 있는 정수의 개수를 출력한다.

 

예제 입력 : 

6
3
72
2
12
7
2
1

예제 출력 : 

68

 

 

접근법 : 

1) 어떻게 풀 것인가?

 

2) 시간복잡도

 

 

3) 공간복잡도

 

 

4) 풀면서 놓쳤던점

 

 

5) 이 문제를 통해 얻어갈 것

 

 

 

C++ 코드 : 

// 카드놓기 5568
#if 1
#pragma warning(disable:4996)
#include <cstdio>
#include <unordered_set>
#include <string>

#define MAX (12)

using namespace std;

int T;
int N, K;   // 이항계수 NCK

int arr[MAX];
bool visit[MAX];
unordered_set<string> cardCnt;
// set<string> cardCnt;   정렬 불필요할때는 unordered가 성능에 유리 (중복제거만 사용)

void input();
void dfs(string num, int remainCnt); // i번째 숫자, 현재완성된 숫자, 남은카운트


int main() {
	//freopen("input.txt", "r", stdin);

	// 1. 입력
	input();

	// 2. 조합 구성해서 set에 던지기
	dfs("", K);

	// 3. 출력
	printf("%d", cardCnt.size());

	return 0;
}

void input() {
	scanf("%d %d", &N, &K);
	for (int i = 0; i < N; i++) {
		scanf("%d", &arr[i]);
	}
}

//    id           num            remainCnt
// i번째 숫자, 현재완성된 숫자, 남은카운트
void dfs(string num, int remainCnt) {

	// ** 탈출조건 - 숫자를 더 붙일 수 없으면 set에 던지고 return
	if (remainCnt == 0) {
		cardCnt.insert(num);
		// 디버깅용 출력 - printf("%s\n", num.c_str());
		return;
	}

	for (int i = 0; i < N; i++) {
		// visit 배열 확인 후 방문
		if (visit[i] == false) {
			visit[i] = true;
			dfs(num + to_string(arr[i]), remainCnt - 1);
			visit[i] = false;
		}
	}
}
#endif