백준 알고리즘 [백트래킹] N과 M (3)_15651_실버3

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
1부터 N까지 자연수 중에서 M개를 고른 수열같은 수를 여러 번 골라도 된다.

 

체감 난이도

실버 3 ~ 실버 5

 

문제 풀이 소감

풀어보지 않았다면 정답을 보고 유형을 파악할 필요 있음 (처음엔 어려움)

 

코드

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

public class Main {
    static int[] arr;
    static int N,M;
    static StringBuilder sb = new 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());
        M = Integer.parseInt(st.nextToken());

        arr = new int[M];

        dfs(0);
        System.out.println(sb);
    }

    static void dfs(int depth) {
       if(depth == M) {
           for (int val : arr) {
               sb.append(val).append(' ');
           }
            sb.append('\n');
           return;
       }

        for (int i = 1; i <= N; i++) {
            arr[depth] = i;
            dfs(depth + 1);

        }
    }
}

 

문제 바로가기

https://www.acmicpc.net/problem/15651