[백준] 6603번 로또 문제 풀어보기
1. 문제
1) 링크
2) 문제
독일 로또는 {1, 2, ..., 49}에서 수 6개를 고른다.
로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 수 중 k(k>6)개의 수를 골라 집합 S를 만든 다음 그 수만 가지고 번호를 선택하는 것이다.
예를 들어, k=8, S={1,2,3,5,8,13,21,34}인 경우 이 집합 S에서 수를 고를 수 있는 경우의 수는 총 28가지이다. ([1,2,3,5,8,13], [1,2,3,5,8,21], [1,2,3,5,8,34], [1,2,3,5,13,21], ..., [3,5,8,13,21,34])
집합 S와 k가 주어졌을 때, 수를 고르는 모든 방법을 구하는 프로그램을 작성하시오.
3) 입력
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 주어진다.
입력의 마지막 줄에는 0이 하나 주어진다.
4) 출력
각 테스트 케이스마다 수를 고르는 모든 방법을 출력한다. 이때, 사전 순으로 출력한다.
각 테스트 케이스 사이에는 빈 줄을 하나 출력한다.
더 자세한 문제의 제한과 예시를 보려면 위의 링크를 클릭해보자.
2. 풀이
이 문제는 마찬가지로 재귀를 활용해서 모든 경우를 다 해보는 문제이다.
k개 중에서 6개를 뽑아야 하므로, 각 index의 숫자를 사용하거나/ 사용하지 않거나 둘 중에서 선택할 수 있다.
그래서 재귀함수의 원형을
algo(int[] a, int index, int count)라는 식으로 작성했는데 여기서 각각이 의미하는것은 말그대로,
- a: 문제에서 입력받은 숫자들
- index: 지금 현재 함수가 와있는 index
- count: 지금까지 로또로 선택된 개수 (이것이 6개가 되면 끝인것임)
위와 같이 적을 수 있고, 재귀함수에서 가능한 모든 경우를 생각해본다면,
- 1. count==6 : 6개를 이미 뽑은 경우 : 이 경우는 더 재귀함수를 돌지 않고 출력해주고 return해주는 과정이 필요하다.
- 2. count가 6이라는 1번 조건에서 걸러지지 않았는데도 index의 값이 입력배열의 범위를 넘어갔을 때 : 이것을 처리해주지 않으면 런타임에러가 날것이다! 모두 해보는 이 방법은 모두 다 안뽑는 그러한 경우도 포함하기 때문에 이렇게 index값이 입력배열의 사이즈와 같아지는 경우 return을 해주어야 한다
- 3. 해당 인덱스의 숫자를 로또 번호로 선택했을 때:
이 경우는 정답배열에다가 숫자를 추가해주고 algo( a, index+1, count+1)을 호출해주면 된다. count를 하나 채웠기 때문이다. 끝난 다음에는 꼭 정답배열에서 다시 숫자를 제거해주는 과정을 거쳐야 한다!! - 4. 해당 인덱스의 숫자를 로또 번호로 선택하지 않았을 때:
이 경우는 아무런 조치를 취하지 않고 algo(a, index+1, count)를 호출해주면 된다. 다음 index의 값을 호출해야 하나, count는 변함이 없기 때문이다.
함수의 순서도 위와 동일하게 출력해주면 되는데 우선 1번과 2번은 정답을 찾았거나 불가능한 경우이기 때문에 이를 먼저 적어줌으로써 return을 해주는 과정이 필요하다. 여기서 중요한것은 3번 4번의 순서이다. 보통 재귀의 경우 사용/사용하지 않음을 다루어주는 코드의 순서가 상관이 없는데 이 문제에서는 오름차순으로 출력을 해주어야 하기 때문에 반드시 3번 코드가 4번 코드보다 위에 있어야 한다. 앞에 있는 index를 먼저 출력해주는 것이 오름차순 출력과 맞기 때문이다. 만약 3번보다 4번코드가 위에 온다면 sorting하는 과정이 추가로 구현되어야 한다.
위의 재귀함수를 구현한 부분코드만 먼저 살펴보겠다.
public static void algo(int[] a, int index, int count){
//1. count가 6개가 다 되었을 때: 출력을 하고 return 해야 함
if (count==6){
for(int num: result){
System.out.print(num+" ");
}
System.out.println();
return;
}
//2. 6개가 다 채워진 것도 아닌데 index가 범위를 넘어갈때
if (index==a.length) return;
//3. 해당 index의 숫자를 사용할때
result.add(a[index]);
algo(a, index+1, count+1);
result.remove(result.size()-1); //마지막에 추가한 것을 다시 제외시켜주는 것이 필요
//4. 해당 index의 숫자를 사용하지 않을때
algo(a, index+1, count);
}위의 설명처럼 1,2,3,4번이 차례로 등장한 것을 알 수 있다.
3. 코드
전체 코드를 살펴보면 아래와 같다.
import java.util.*;
public class Main{
public static ArrayList<Integer> result;
public static void algo(int[] a, int index, int count){
//1. count가 6개가 다 되었을 때: 출력을 하고 return 해야 함
if (count==6){
for(int num: result){
System.out.print(num+" ");
}
System.out.println();
return;
}
//2. 6개가 다 채워진 것도 아닌데 index가 범위를 넘어갈때
if (index==a.length) return;
//3. 해당 index의 숫자를 사용할때
result.add(a[index]);
algo(a, index+1, count+1);
result.remove(result.size()-1); //마지막에 추가한 것을 다시 제외시켜주는 것이 필요
//4. 해당 index의 숫자를 사용하지 않을때
algo(a, index+1, count);
}
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
while(true){
int n=sc.nextInt();
if (n==0) break;
int a[]=new int [n];
for(int i=0; i<n; i++){
a[i]=sc.nextInt();
}
result=new ArrayList<>();
algo(a, 0, 0); // (입력, index, count)
System.out.println(); //테스트케이스 사이에 한 줄 띄어야 함
}
}
}