문제 출처

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

문제 설명

자연수 N과 M이 주어 졌을 때, 조건을 만족하는 길이가 M인 수열을 모두 출력하라.
같은 수를 여러개 골라도 되지만, 고른 수열은 비내림차순이어야 한다.

비내림차순 -> a1<=a2<=...<=ak-1<=ak

접근 방법

dfs를 이용하되, visted는 이용하지 않는다.
dfs 내부의 for를 사용할 때, 초기값은 start, 다음 dfs의 start 인자는 i로 두어서 이전 값보다 큰 값이 다음 조합에 올 수 있게한다.

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

public class N과_M_4 {

    public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static int com[];

    public static void dfs(int depth, int length, int N,int start)  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 = start; i<=N; i++){
            com[depth] = i;
            dfs(depth+1,length,N, i);
        }
    }

    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,1);

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

    }

}

Review

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

public class N과_M_4_review {

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

    public static void dfs(int depth, int length, int start, int N) throws IOException {
        if(depth == length){
            sb = new StringBuilder();
            for(int i : com){
                sb.append(i).append(" ");
            }
            sb.append("\n");
            bw.write(sb.toString());
            return;
        }

        for(int i = start; i<=N; i++){
            com[depth] = i;
            dfs(depth+1, length, i, 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,1,N);

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

}

알게된 점

처음 문제를 제출할 때, 수열의 길이 M, 가능한 최대숫자 N을 바꿔서 제출해서 런타임에러(ArrayIndexOutOfBounds)가 떴었다.
문제를 제출하기 전에 꼭 코드를 한 번 더 읽어보는 습관을 기르자

문제푼 흔적

Review