[Java] 백준 15650번: N과 M (2)

문제

일단 생각하기!

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열은 중복이 아닌 조합이다.
  [Java] 프로그래머스 1단계: 소수 만들기에서 주어진 숫자 중 3개를 뽑아 더하는 것을 구현한 로직이 있었는데 오늘 라이브 강의를 들으며 그 부분이 나왔다!
• for문을 이용한다면 위와 같이 풀면 되고, 만약 몇개를 뽑을지 모를땐 재귀함수를 이용하면 된다. 현재 수열의 몇번째 길이를 더하고 있는지 명시하는 cnt, for문이 몇부터 N까지 작동할지 명시해주는 start를 매개변수로 가지는 재귀함수를 for문이 한번 돌고 난 후 호출해준다. 이때, cnt에는 cnt + 1을, start에는 i+1을 넣어준다.

풀이

package BJ;

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

/**
 * 
 * @author 김유나
 * 2023-08-02
 * [문제] 백준 15650번 N과 M(2)
 * - 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열을 구하는 프로그램을 작성해라.
 * [아이디어] 
 * - 중복 없이 M개를 고른 수열은 중복이 아닌 조합이다. 재귀 함수를 이용한 중복 없는 조합을 구현하면 된다. 
 */

public class BJ_15650_N과M2_김유나 {
	static int numbers[]; // 수열을 저장할 배열
	static int N, M;
	static StringBuilder sb = new StringBuilder(); // StringBuilder 사용
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken()); // N 입력 받기
		M = Integer.parseInt(st.nextToken()); // M 입력 받기
	
		numbers = new int[M]; // M 길이의 numbers 배열 생성
		
		comb(0, 1); // cnt : 0, start : 1
		System.out.println(sb); // StringBuilder 출력
	}
	static void comb(int cnt, int start) {
		if (cnt == M) { // if cnt가 M의 크기에 도달했을때
			for (int i = 0; i < M; i++) {
				sb.append(numbers[i]); // 출력 위해 StringBuilder에 append
				sb.append(" ");
			}
			sb.append("\n");
			return;
		}
		
		for (int i = start; i <= N; i++) {
			numbers[cnt] = i; // 수열의 첫 자리에 1부터 N까지 넣기
			comb(cnt + 1, i + 1); // cnt와 i 각각 +1 해주기
		}
	}
}