[백준] 15652번 N과 M - 4 (C++, JAVA)

15652번: N과 M (4)

N개 중에 중복 포함, 순서 상관없이 M개를 뽑는 중복 조합 문제이다.

앞의 값보다 크거나 같은 값일 경우에만 벡터에 넣어주고 카운트가 M일 때 출력해주면 된다.

 

< C++ 코드 >

#include <iostream>
#include <vector>
using namespace std;
vector <int> v;

int cnt = 0;
void multiCombination(int N, int M, int start) {
	if (cnt == M) {
		for (int i = 0; i < v.size(); i++) {
			cout << v[i] << " ";
		}
		cout << "\n";
	}
	else {
		for (int i = 0; i < N; i++) {
			if (start <= i) {
				v.push_back(i + 1);
				cnt++;
				multiCombination(N, M, i);
				v.pop_back();
				cnt--;
			}
		}
	}
}

int main() {
	int N, M;
	cin >> N >> M;

	multiCombination(N, M, -1);

	return 0;
}

 

< JAVA 코드 >

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

public class BOJ_15652_N과M_4 {
	private static StringBuilder sb = new StringBuilder();
	private static int N, M;
	private static int arr[];
	
	public static void combination(int cnt, int idx) {
		if(cnt == M) {
			for(int val : arr) sb.append(val).append(' ');
			sb.append('\n');
			return;
		}
		for(int i = idx; i < N; i++) {
			arr[cnt] = i + 1;
			combination(cnt + 1, i);
		}
	}
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken()); M = Integer.parseInt(st.nextToken()); arr = new int[M];
		combination(0, 0);
		System.out.println(sb);
	}
}