[백준BOJ] 5568번 카드 놓기.java

 

백준 저지에서 카드 놓기를 자바를 통해 풀어 보았다. 

 

https://www.acmicpc.net/problem/5568

5568번: 카드 놓기

5568번 카드 놓기.java

GitHub - tomy9729/Algorithm: 🐗 내가 직접 작성한 내 코드 🐗

 

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

설명

재귀 함수와 백트래킹을 통해 조합을 구현하는 문제이다. 

 

일반적인 조합 문제와 비슷하지만 한 가지 특이점이 있다. 배열에 들어 있는 값을 기준으로 조합을 구하는게 아니라 배열의 각 index에 대해서 조합을 구해야한다. 배열에 동일한 값들이 올 수 있기 때문에 만약 값을 기준으로 조합을 구하게 되면 답보다 부족한 조합의 수를 구하게 될 것이다.

코드

//5568번 카드 놓기.java
package week3;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class 카드_놓기_5568 {
	private static int n;
	private static int k;
	private static int[] nums;
	private static List<String> answer = new ArrayList<>();
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(bf.readLine());
		k = Integer.parseInt(bf.readLine());
		nums = new int[n];
		for(int i=0;i<n;i++) {
			nums[i]=Integer.parseInt(bf.readLine());
		}
		List<Integer> temp = new ArrayList<>();
		sol(k,temp);
		System.out.println(answer.size());
	}
	public static void sol(int count, List<Integer> k_nums) {
		if(count==0) {
			String result = new String();
			for(int i=0;i<k;i++) {
				result+=nums[k_nums.get(i)];
			}
			if(!answer.contains(result)) {
				answer.add(result);
			} 
			return;
		}
		
		for(int i=0;i<n;i++) {
			if(!k_nums.contains(i)) {//index를 기준으로 조합을 구한다.
				k_nums.add(i);
				sol(count-1,k_nums);
				k_nums.remove(k_nums.size()-1);
			}
		}
	}
}