[Baekjoon] 5568_카드 놓기

Silver IV

문제(출처: https://www.acmicpc.net/problem/5568)

---

< 카드 놓기 >

 

문제 풀이 

 

조합을 사용하여 정수를 만든 후 중복을 판단하기 위해 set에 넣은 후 set의 개수를 출력한다.

 

 my solution (Java)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;

public class _5568_ { // 카드 놓기
	static String arr[], result[];
	static boolean visited[];
	static Set<Integer> set;

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(bf.readLine());
		int k = Integer.parseInt(bf.readLine());

		arr = new String[n];
		result = new String[k];
		visited = new boolean[n];
		set = new HashSet<>();

		for (int i = 0; i < n; i++) {
			arr[i] = bf.readLine();
		}

		search(0, k);

		System.out.println(set.size());
	}

	private static void search(int idx, int k) {
		if (idx == k) {
			String str = "";
			for (int i = 0; i < k; i++) {
				str += result[i];
			}
			set.add(Integer.parseInt(str));

			return;
		}

		for (int i = 0; i < arr.length; i++) {
			if (!visited[i]) {
				visited[i] = true;
				result[idx] = arr[i];
				search(idx + 1, k);
				visited[i] = false;
			}
		}
	}
}

 

Main

변수)
n : 카드 수
k : 선택하는 카드 수
arr : 카드 저장 배열
result : 선택한 카드 저장 배열
visited : 방문 여부
set : 조합한 정수 저장

 

- 카드 수(n), 선택하는 카드 수(k) 입력

- 카드를 입력받아 배열에 저장(arr)

- search 함수 호출

- 만들 수 있는 정수의 개수(set의 크기) 출력

 

Search

- k개만큼 카드를 선택했다면 set에 추가

- 카드 수(n)만큼 반복

: 아직 사용하지 않은 카드라면 사용 후 다음 카드를 선택하기 위해 search 함수 호출

: search 함수 호출 후 다음 조합을 위해 사용하지 않음으로 저장

---

---