백준 5568번 카드 놓기

< 백준 5568번 카드 놓기 - 마포 코딩박 >

사용한 알고리즘: 구현


 N개의 카드 중 K개를 뽑아 만들 수 있는 정수 개수를 구하는 문제였습니다.
 사실 2<= K <= 4 여서 그냥 노가다로 구했습니다.

문제풀이는 다음과 같습니다.

(1) (코드 8~9)
 주어진 N개 카드 중 K 개로 만들 수 있는 정수를 중복을 피하기 위해 set을 만들어 저장했습니다.
 예를들어 1, 2, 12 로 수를 만드는 경우, 1 2 12 = 12 1 2 = 1212 인 중복이 발생합니다.

(2) (코드 11~59)
 K개의 수로 정수를 만드는 함수를 만들어 줍니다.
 K = 2, 3, 4 중 하나이니 이 경우를 직접 손으로 구현했습니다....... (보다 나은 풀이가 많겠죠...)

(3) (코드 60~70)
 N개의 카드 중 K 개를 뽑는 것을 재귀함수로 구현했습니다.
 i 번째 카드를 뽑냐, 뽑지않냐만 구현해주면 됩니다.

(4) (코드 83)
 만들어진 set의 크기가 곧 (중복을 제거하고)만들어진 정수의 개수입니다.

	#include <iostream>
	#include <string>
	#include <set>
	#include <vector>
	using namespace std;
	int N, K;
	// 만들 수 있는 정수 개수 저장
	set<string> S;
	vector<string> V;
	// 주어진 K 개의 정수로 숫자만들기
	void MIX(vector<string> temp){
	string a = temp[0];
	string b = temp[1];
	if(K==2){
	S.insert(a+b);
	S.insert(b+a);
	}
	else if(K==3){
	string c = temp[2];
	S.insert(a+b+c);
	S.insert(a+c+b);
	S.insert(b+a+c);
	S.insert(b+c+a);
	S.insert(c+a+b);
	S.insert(c+b+a);
	}
	else{
	string c = temp[2];
	string d = temp[3];
	S.insert(a+b+c+d);
	S.insert(a+b+d+c);
	S.insert(a+c+b+d);
	S.insert(a+c+d+b);
	S.insert(a+d+c+b);
	S.insert(a+d+b+c);
	S.insert(b+a+c+d);
	S.insert(b+a+d+c);
	S.insert(b+c+a+d);
	S.insert(b+c+d+a);
	S.insert(b+d+a+c);
	S.insert(b+d+c+a);
	S.insert(c+a+b+d);
	S.insert(c+a+d+b);
	S.insert(c+b+a+d);
	S.insert(c+b+d+a);
	S.insert(c+d+a+b);
	S.insert(c+d+b+a);
	S.insert(d+a+b+c);
	S.insert(d+a+c+b);
	S.insert(d+b+a+c);
	S.insert(d+b+c+a);
	S.insert(d+c+a+b);
	S.insert(d+c+b+a);
	}
	}
	// N개 카드중 K개 뽑기
	void Choose(int curr, vector<string> temp){
	if(temp.size()==K){
	MIX(temp);
	return;
	}
	if(curr>=N) return;
	// 현재 카드를 뽑지 않고 다음 카드로
	Choose(curr+1, temp);
	// 현재 카드를 뽑고 다음 카드로
	temp.push_back(V[curr]);
	Choose(curr+1,temp);
	}
	int main(){ios::sync_with_stdio(false);cout.tie(NULL);cin.tie(NULL);
	cin >> N >> K;
	for(int i=0; i<N; ++i){
	string a;
	cin >> a;
	V.push_back(a);
	}
	vector<string> tt;
	Choose(0, tt);
	cout<<S.size()<<'\n';
	return 0;
	}

view raw BOJ 5568.cpp hosted with ❤ by GitHub