Skip to content

BOJ_5568_카드 놓기 #45

Open
Open

Description

@changicho

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;
}

Activity

  1. added this to the day5 milestone on Jan 10, 2020
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    clear정답코드

    Projects

    No projects

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions