백준 6603 로또
1. 문제 링크
2. 풀이
- 이 문제는 조합의 대표 유형이다.
- 조합은 순서를 고려하지 않기 때문에 아래의 경우는 1개로 카운트 한다.
- [1, 2, 3] / [1, 3, 2] / [2, 1, 3] - [1, 2, 3] 에서 2개를 뽑는 경우를 생각해본다.
- 가능한 경우는 [1, 2] / [1, 3] / [2, 3] 총 3개이다.
- 처음 1을 뽑고 나서 1이 포함된 모든 경우를 구한 뒤부터는 1은 나오지 않는다.
- 따라서 getLotto에서 재귀 호출 시 i + 1을 하여 다음 depth에서 이전 depth에서 고려된 수는 제외하도록 했다.
3. 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
while (true) {
String[] line = br.readLine().split(" ");
int n = Integer.parseInt(line[0]);
if (n == 0)
break;
int[] numbers = new int[line.length - 1];
boolean[] visit = new boolean[line.length - 1];
for (int i = 1; i <= n; i++) {
numbers[i - 1] = Integer.parseInt(line[i]);
}
getLotto(0, 0, numbers, visit);
System.out.println();
}
}
static void getLotto(int depth, int index, int[] numbers, boolean[] visit) {
if (depth == 6) {
for (int i = 0; i < visit.length; i++) {
if (visit[i]) {
System.out.print(numbers[i] + " ");
}
}
System.out.println();
return;
}
for (int i = index; i < numbers.length; i++) {
if (!visit[i]) {
visit[i] = true;
// 중복을 피하기 위해, 다음 depth 에서 이전의 수를 고려하지 않도록 i + 1번째부터 시작하도록 한다.
getLotto(depth + 1, i + 1, numbers, visit);
visit[i] = false;
}
}
}
}
4. 채점 결과
5. 느낀 점
- 조합의 전형적인 문제였으며, 익숙해져야하는 유형이다.
- 재귀를 들어갔다 나오면서 visit 배열을 원래 상태로 만들어야한다.
Author And Source
이 문제에 관하여(백준 6603 로또), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@gan/백준-6603-로또저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)