티스토리 뷰
이 문제는 조합을 구하는 문제입니다.
중복이 없는 조합의 경우 [1, 2, 3, 4]가 주어졌을 때, [1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]를 선택할 수 있습니다. 즉, [1, 2]와 [2, 1]은 같은 숫자 조합을 의미합니다.
한번 뽑힌 조합은 다시 선택하지 않기 때문에 숫자 하나를 선택하면 이후에는 그 다음 수들만 확인하면 됩니다.
자바 코드는 다음과 같습니다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] input = br.readLine().split(" ");
int n = Integer.parseInt(input[0]);
int m = Integer.parseInt(input[1]);
combination(new boolean[n], 0, m);
}
private static void combination(boolean[] selected, int r, int k) {
// 뽑아야 하는 수를 모두 뽑은 경우 출력
if (k == 0) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < selected.length; i++) {
if (selected[i]) {
sb.append(i + 1).append(" ");
}
}
System.out.println(sb);
return;
}
// r부터 확인하면서
for (int i = r; i < selected.length; i++) {
selected[i] = true; // 뽑은 경우
combination(selected, i + 1, k - 1); // i를 뽑았다면 그 다음부터 확인해야하므로 i + 1, 하나를 뽑았기 때문에 뽑아야 하는 수 감수 k - 1
selected[i] = false; // 뽑지 않은 경우
}
}
}
'알고리즘' 카테고리의 다른 글
[백준알고리즘] 15652 - N과 M (4) (0) | 2021.05.06 |
---|---|
[백준알고리즘] 15651 - N과 M (3) (0) | 2021.05.04 |
[백준알고리즘] 15649 - N과 M (1) (0) | 2021.04.29 |
[프로그래머스] 카펫 (0) | 2021.04.23 |
[프로그래머스] 구명보트 (0) | 2021.04.22 |
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- array
- map
- java
- 순열
- DFS
- Baekjoon
- CodeCommit
- string
- SWIFT
- 에라토스테네스의 체
- search
- cloudfront
- AWS
- Combination
- sort
- programmers
- spring
- 프로그래머스
- BFS
- EC2
- CodePipeline
- 수학
- CodeDeploy
- ECR
- permutation
- Algorithm
- 소수
- ionic
- 조합
- Dynamic Programming
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
글 보관함