Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

BOJ_5568_카드 놓기 #45

Open
changicho opened this issue Jan 10, 2020 · 0 comments
Open

BOJ_5568_카드 놓기 #45

changicho opened this issue Jan 10, 2020 · 0 comments
Labels
clear 정답코드
Milestone

Comments

@changicho
Copy link
Owner

5568. 카드 놓기

링크

난이도 정답률(_%)
Silver V 50

설계

완전 탐색

가능한 모든 조합을 구해야 한다.

최대 카드의 수가 10이고, 뽑는 카드의 수가 4이므로 가능한 모든 조합을 뽑았을 때 시간복잡도는 10^4이므로 시간 내에 풀 수 있다.

unique

unique한 수를 뽑기 위해 unique함수를 이용했다.

정리

내 코드 빠른 코드
0 ms

고생한 점

코드

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

vector<string> cards;
vector<int> numbers;
int N, K;

bool visited[10] = { 0, };

void dfs(int cardCount, string number) {
	if (cardCount == K) {
		numbers.push_back(stoi(number));
		return;
	}

	for (int i = 0; i < cards.size(); i++) {
		if (visited[i]) continue;

		string new_number = number + cards[i];
		visited[i] = 1;
		dfs(cardCount + 1, new_number);
		visited[i] = 0;
	}
}

void solution() { 
	cin >> N >> K;
	
	for (int i = 0; i < N; i++) {
		string card;
		cin >> card;
		cards.push_back(card);
	}

	// find all possible combination
	dfs(0, "");

	sort(numbers.begin(), numbers.end());
	numbers.erase(unique(numbers.begin(), numbers.end()), numbers.end());

	cout << numbers.size() << "\n";
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	solution();

	return 0;
}
@changicho changicho added the clear 정답코드 label Jan 10, 2020
@changicho changicho added this to the day5 milestone Jan 10, 2020
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
clear 정답코드
Projects
None yet
Development

No branches or pull requests

1 participant