[백준] 15651번 N과 M (3) java

1. 백준 15651번 문제

1.문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

1부터 N까지 자연수 중에서 M개를 고른 수열
같은 수를 여러 번 골라도 된다.

2.입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 7)

3.출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

2. 문제 해석

1) 1 ~ N 까지의 수 중 M 개를 선택하여 조합하기. (길이가 M이다)

2) 중복해서 조합 가능.

3) 1 부터 N까지 M의 길이 및 크기로 중복을 허용해서 조합할 수 있는 수를 오름차순으로 나열하는 문제입니다.

3. 문제 풀이

import java.util.Scanner;

public class Study {

  public static int N, M;
  public static int[] selected;
  public static StringBuilder sb = new StringBuilder();

  public static void main(String[] args) {
      Scanner in = new Scanner(System.in);

      N = in.nextInt();//조합할 숫자를 입력
      M = in.nextInt();//선택할 깊이를 입력

      selected = new int[M]; //깊이 만큼 배열을 생성한다.

      rec_func(0);//0일때 부터 재귀함수 실행
      System.out.print(sb); //sb에 쌓인 string 값을 모두 출력
  }

  public static void rec_func(int depth) {
      //phase1 : 설명을 위한 페이즈 구분
      if (depth == M) { //깊이가 처음 설정한 깊이 값이 되기 전까지 배열의 값을 가져와 StringBuilder sb append 해줍니다.
          for (int i = 0; i < M; i++) {
              sb.append(selected[i] + " ");
          }
          sb.append("ck");
          sb.append('\n');
          return;
      }
      //phase2 : 설명을 위한 페이즈 구분
      for (int i = 1; i <= N; i++) { //조합할 숫자보다 i 값이 작다면,
          selected[depth] = i; //깊이가 아직 처음 설정한 깊이가 아닐때 그 값을 대입합니다.
          //selected[0]에는 현재 1이 들어가 있는 상태.
          //selected[0]에 1이 들어간 상태로 rec_func를 call 하게 되면
          //rec_func(1)이 실행이 되고 depth는 아직 M 값이 아니라면 phase2로 진입하게 됩니다.
          //phase2로 진입을 하게 된다면 selected[0]에 1이 들어간 상태로 selected[1]으로 for문의 i값이 1부터 1씩 증가하면서 대입됩니다.
          //selected[1]으로 for문의 i값이 1부터 1씩 증가하면서 대입된 후에 rec_func(2)가 실행이 됩니다.
          //만약 depth가 M과 일치하게 된다면 StringBuilder sb 변수에 배열에 들어있던 값이 차례대로 저장되게 됩니다.
          rec_func(depth + 1);
      }
  }
}

출력 결과

3
2
1 1 ck
1 2 ck
1 3 ck
2 1 ck
2 2 ck
2 3 ck
3 1 ck
3 2 ck
3 3 ck