https://www.acmicpc.net/problem/15652
15652호: N과 M (4)
'추천 관련글,
문제의 조건을 만족하는 일련의 숫자를 한 줄에 하나씩 인쇄합니다.
중복 시퀀스는 한 번 이상 인쇄해서는 안 되며 각 시퀀스는 공백으로 구분하여 인쇄해야 합니다.
시퀀스는 알파벳 오름차순으로 인쇄됩니다.
www.acmicpc.net
(문제)
주어진 자연수 N과 M이 주어지면 다음 조건을 만족하는 길이 M의 모든 시퀀스를 찾는 프로그램을 작성하십시오.
- 1부터 N까지 M개의 선택된 자연수 시퀀스
- 같은 번호로 두 번 이상 전화를 걸 수 있습니다.
- 선택한 순서는 내림차순이 아니어야 합니다.
- 길이 K의 시퀀스 A는 A1입니다.
≤ A2 ≤ … ≤ AK-1 ≤ AK가 충족되면 순서가 내림차순이 아니라고 합니다.
- 길이 K의 시퀀스 A는 A1입니다.
(기입)
자연수 N과 M은 첫 줄에 주어진다.
(1≤M≤N≤8)
3 1
(누르다)
문제의 조건을 만족하는 일련의 숫자를 한 줄에 하나씩 인쇄합니다.
중복 시퀀스는 한 번 이상 인쇄해서는 안 되며 각 시퀀스는 공백으로 구분하여 인쇄해야 합니다.
시퀀스는 알파벳 오름차순으로 출력되어야 합니다.
하나
2
삼
(생각하다)
중복을 허용하는 조합 문제
재귀적으로 해결
(소스 코드)
import java.util.Scanner;
public class Main {
static int N, M;
static int() numbers;
static StringBuilder sb = new StringBuilder();
public static void main(String() args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
M = sc.nextInt();
numbers = new int(M);
combination(0, 1);
System.out.println(sb);
}
//중복O 조합
private static void combination(int cnt, int start) {
//기저조건
if (cnt == M) {
for (int i = 0; i < M; i++) {
sb.append(numbers(i) + " ");
}
sb.append("\n");
return;
}
//유도파트
for (int i = start; i <= N; i++) {
numbers(cnt) = i;
combination(cnt + 1, i);
}
}
}