티스토리 뷰

www.acmicpc.net/problem/15657

 

15657번: N과 M (8)

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열

www.acmicpc.net

 

문제는 위와 같으며 중복 조합을 구하는 문제입니다. 중복 조합이기 때문에 수를 선택할 시작 위치를 현재 선택한 인덱스 다음이 아니라 현재 선택한 인덱스로 지정하게 됩니다.

 

자바 코드는 다음과 같습니다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

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]);

        int[] nums = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        Arrays.sort(nums);

        combination(nums, new int[n], n, m, 0, 0);
    }

    private static void combination(int[] nums, int[] selected, int n, int m, int start, int k) {
        if (k == m) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < m; i++) {
                sb.append(selected[i]).append(" ");
            }
            System.out.println(sb);
            return;
        }

        for (int i = start; i < n; i++) {
            selected[k] = nums[i];
            combination(nums, selected, n, m, i, k + 1);
        }
    }
}
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2024/12   »
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
글 보관함