[BOJ] 5568 : 카드놓기

진승범·2021년 10월 6일
0
post-thumbnail
post-custom-banner

출처 : https://www.acmicpc.net/problem/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개를 선택해서 만들 수 있는 정수의 개수를 구하는 프로그램을 작성하시오.

💻 입력/출력


📝 풀이


본 문제의 설명은 재귀 카테고리에 있는 문제이며, 내가 생각하는 문제의 요점은
바로 중복이 허용 된다는 것이다. 즉 5개의 카드 {1,1,2,3,4} 에서 3개를 뽑는다고 하면 [1,1,2],[1,2,1]
이런식으로 순서가 바뀌어도 해당 값은 정수가 만들어지기 때문에 허용이 된다. 또한 한 개의 정수가 만들어진다 하더라도 그 방법은 다양할수도 있기 때문에 그런 중복은 허용이 되지 않는다 즉, 정수의 갯수만 파악하여야 한다.

위 문제를 풀기 위해선 가장 먼저 정수가 어떤 방식으로 만들어질지 생각해봐야 한다.
위와 같은 예시에서 3개의 카드를 뽑는 경우의 수는

[1,1,2][1,1,3] [1,1,4][1,2,3] [1,2,4][1,2,1] [1,3,4][1,3,1] [1,3,2] ···
이런식으로 진행되게 된다. 이러한 패턴을 파악하기 쉽게 구성한다면

1
	1
   		2 [1,1,2]
		3 [1,1,3]
		4 [1,1,4]
	2
		3 [1,2,3]
		4 [1,2,4]
		1 [1,2,1]
	3
		4 [1,3,4]
		1 [1,3,1]
		2 [1,3,2]
	4
		1 [1,4,1]
		2 [1,4,2]
		3 [1,4,3]
2

       ·
       ·
       ·
       ·
       ·

각 정수의 자릿수를 level[0,1,2] 라고 한다면
0 level의 반복수는 n번
1 level은 n-1번
2 level은 n-2번이다.

우리는 n=5인 경우를 살펴봤으니, 세 단계에서 각각 5번 4번 3번을 반복하여 정수를 추출해내는 것이다. 그리고 재귀 함수 맨 앞에 level이 1의 자리 정수를 구할 때, String으로 해당 정수를 추가시켜서 ArrayList.contains() 메소드를 통해 있는 지 확인한 수 false라면 해당 정수를 추가시킨다.

내가 제시한 기준에서 나는 10의 자리수가 바뀌는 과정을 배열의 재조정을 통해 풀었다.
코드를 통해 알아보자

📋 코드


public class card {

	static int k = 0;
	static int n = 0;
	static ArrayList<String> jungsuList = new ArrayList<String>();

	public static void main(String[] args) throws NumberFormatException, IOException {
		ArrayList<Integer> arr = new ArrayList<Integer>();
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		n = Integer.parseInt(br.readLine());
		k = Integer.parseInt(br.readLine());
		for (int q=0; q<n; q++) {
			arr.add(Integer.parseInt(br.readLine()));
		}
		
		pushBlock(arr,"",0);
		
		System.out.println(jungsuList.size());
		
	}
	
	public static void pushBlock(ArrayList<Integer> a,String number, int count) {
		String abc = number;
		
		if (count == k-1) {
			for (int k=count; k<n; k++) {
				number += String.valueOf(a.get(k));
				if (!jungsuList.contains(number)) { // arraylist에 같은 수가 있는지 확인
					jungsuList.add(number);
				}
				number = abc;
			}
			return;
		}
		
		for (int i=count; i<n; i++) {
			number += String.valueOf(a.get(count));
			pushBlock(a,number,count+1);
			int temp = a.get(count);
			a.remove(count);
			a.add(temp);
			
			number = abc;
		}
	}
	
}
post-custom-banner

0개의 댓글