문제 출처

단계별로 풀어보기 > 백트래킹 > N과 M (3)
https://www.acmicpc.net/problem/15651

문제 설명

자연수 N과 M이 주어질 때, 1~N까지 자연수 중 M개를 고른 중복이 허용되는 수열을 모두 구하라.

접근 방법

기존 N과 M 문제들에서 visited, 즉 방문 여부를 체크하지 않는 백트래킹(dfs)을 구현하면 된다.

import java.io.*;
import java.util.StringTokenizer;

public class N과_M_3 {

    public static int[] com;
    public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void dfs(int depth, int length, int N) throws IOException{

        if(depth == length){
            StringBuilder sb = new StringBuilder();
            for(int i : com){
                sb.append(i).append(" ");
            }
            sb.append("\n");
            bw.write(sb.toString());
            return;
        }

        for(int i = 1; i<=N; i++){
            com[depth] = i;
            dfs(depth+1, length, N);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        com = new int[M];

        dfs(0,M,N);

        bw.flush();
        bw.close();
        br.close();


    }
}

Review

import java.io.*;
import java.util.StringTokenizer;

public class N과_M_3_review {


    public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    public static int com[];

    public static void dfs(int depth, int length, int N) throws IOException{
        if(depth == length){
            StringBuilder sb = new StringBuilder();

            for(int k : com){
                sb.append(k).append(" ");
            }
            sb.append("\n");
            bw.write(sb.toString());
            return;
        }

        for(int i = 1; i<=N; i++){
            com[depth] = i;
            dfs(depth+1,length,N);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        com = new int[M];

        dfs(0,M,N);

        bw.flush();
        bw.close();
        br.close();
    }

}

알게된 점

1,2번 문제들 보다 더 쉬운 것 같다.

문제푼 흔적

Review