골드에그

[문제 개요]

N 개의 자연수에서 M 개를 고른 수열을 출력하시오.

각 문제마다 조건이 추가된다. 이 N 과 M 시리즈는 재귀함수(DFS)의 본질을 이해하고, 우리가 흔히 접할 수 있는 순열 및 조합 문제를 풀 수 있는 기초가 되기 때문에 꼭 풀어보는 것을 권장한다.

N과 M (1)

+ 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

+ 자기 자신은 제외하고 남은 수열을 출력한다.

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

public class Main {
    private static int N, M;
    private static int[] combinations;
    private static boolean[] visited;
    private static StringBuilder sb = new StringBuilder();
    private static void dfs(int index, int depth) {
        // 종료 조건
        if (depth == M) {
            for (int i = 0; i < M; i++) {
                sb.append(combinations[i]).append(" ");
            }
            sb.append("\n");
            return;
        }
        for (int i = 0; i < N; i++) {
            if (!visited[i]) {
                combinations[depth] = i + 1;
                visited[i] = true;
                dfs(i, depth + 1);
                visited[i] = false;
            }
        }
    }
    public static void main(String[] args) throws IOException {
        StringTokenizer st;

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        combinations = new int[N];
        visited = new boolean[N];
        dfs(0,0);
        System.out.println(sb.toString());
    }
}

N과 M (2)

+ 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

+ 수열은 오름차순이어야 한다. (자기 자신보다 작은 숫자를 그 다음 숫자로 만들어서는 안 된다.)

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

public class Main {
    private static int N, M;
    private static int[] combinations;
    private static boolean[] visited;
    private static StringBuilder sb = new StringBuilder();
    private static void dfs(int index, int depth) {
        // 종료 조건
        if (depth == M) {
            for (int i = 0; i < M; i++) {
                sb.append(combinations[i]).append(" ");
            }
            sb.append("\n");
            return;
        }
        for (int i = index; i < N; i++) {
            if (!visited[i]) {
                combinations[depth] = i + 1;
                visited[i] = true;
                dfs(i, depth + 1);
                visited[i] = false;
            }
        }
    }
    public static void main(String[] args) throws IOException {
        StringTokenizer st;

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        combinations = new int[N];
        visited = new boolean[N];
        dfs(0,0);
        System.out.println(sb.toString());
    }
}

N과 M (3)

+ 1부터 N까지 자연수 중에서 M개를 고른 수열

+ 같은 수를 여러 번 골라도 된다.

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

public class Main {
    private static int N, M;
    private static int[] combinations;
    private static StringBuilder sb = new StringBuilder();
    private static void dfs(int index, int depth) {
        // 종료 조건
        if (depth == M) {
            for (int i = 0; i < M; i++) {
                sb.append(combinations[i]).append(" ");
            }
            sb.append("\n");
            return;
        }
        for (int i = 0; i < N; i++) {
            combinations[depth] = i+1;
            dfs(i, depth + 1);
        }
    }
    public static void main(String[] args) throws IOException {
        StringTokenizer st;

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        combinations = new int[N];
        dfs(0,0);
        System.out.println(sb.toString());
    }
}

N과 M (4)

+ 1부터 N까지 자연수 중에서 M개를 고른 수열

+ 같은 수를 여러 번 골라도 된다.

+ 수열은 오름차순이어야 한다. (자기 자신보다 작은 숫자를 그 다음 숫자로 만들어서는 안 된다.)

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

public class Main {
    private static int N, M;
    private static int[] combinations;
    private static StringBuilder sb = new StringBuilder();
    private static void dfs(int index, int depth) {
        // 종료 조건
        if (depth == M) {
            for (int i = 0; i < M; i++) {
                sb.append(combinations[i]).append(" ");
            }
            sb.append("\n");
            return;
        }
        for (int i = index; i < N; i++) {
            combinations[depth] = i+1;
            dfs(i, depth + 1);
        }
    }
    public static void main(String[] args) throws IOException {
        StringTokenizer st;

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        combinations = new int[N];
        dfs(0,0);
        System.out.println(sb.toString());
    }
}

N과 M (5)

+ 자기 자신은 제외하고 남은 수열을 출력한다.

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

public class Main {
    private static int N, M;
    private static int[] combinations, items;
    private static boolean[] visited;
    private static StringBuilder sb = new StringBuilder();
    private static void dfs(int index, int depth) {
        // 종료 조건
        if (depth == M) {
            for (int i = 0; i < M; i++) {
                sb.append(combinations[i]).append(" ");
            }
            sb.append("\n");
            return;
        }
        for (int i = 0; i < N; i++) {
            if(!visited[i]) {
                combinations[depth] = items[i];
                visited[i] = true;
                dfs(i, depth + 1);
                visited[i] = false;
            }
        }
    }
    public static void main(String[] args) throws IOException {
        StringTokenizer st;

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        items = new int[N];
        combinations = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            items[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(items);
        visited = new boolean[N];
        dfs(0,0);
        System.out.println(sb.toString());
    }
}

N과 M (6)

+ 수열은 오름차순이어야 한다. (자기 자신보다 작은 숫자를 그 다음 숫자로 만들어서는 안 된다.)

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

public class Main {
    private static int N, M;
    private static int[] combinations, items;
    private static boolean[] visited;
    private static StringBuilder sb = new StringBuilder();
    private static void dfs(int index, int depth) {
        // 종료 조건
        if (depth == M) {
            for (int i = 0; i < M; i++) {
                sb.append(combinations[i]).append(" ");
            }
            sb.append("\n");
            return;
        }
        for (int i = index; i < N; i++) {
            if(!visited[i]) {
                combinations[depth] = items[i];
                visited[i] = true;
                dfs(i, depth + 1);
                visited[i] = false;
            }
        }
    }
    public static void main(String[] args) throws IOException {
        StringTokenizer st;

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        items = new int[N];
        combinations = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            items[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(items);
        visited = new boolean[N];
        dfs(0,0);
        System.out.println(sb.toString());
    }
}

N과 M (7)

+ 같은 수를 여러 번 골라도 된다.

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

public class Main {
    private static int N, M;
    private static int[] combinations, items;
    private static boolean[] visited;
    private static StringBuilder sb = new StringBuilder();
    private static void dfs(int index, int depth) {
        // 종료 조건
        if (depth == M) {
            for (int i = 0; i < M; i++) {
                sb.append(combinations[i]).append(" ");
            }
            sb.append("\n");
            return;
        }
        for (int i = 0; i < N; i++) {
            combinations[depth] = items[i];
            dfs(i,depth + 1);
        }
    }
    public static void main(String[] args) throws IOException {
        StringTokenizer st;

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        items = new int[N];
        combinations = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            items[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(items);
        dfs(0,0);
        System.out.println(sb.toString());
    }
}

N과 M (8)

+ 같은 수를 여러 번 골라도 된다.

+ 수열은 오름차순이어야 한다. (자기 자신보다 작은 숫자를 그 다음 숫자로 만들어서는 안 된다.)

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

public class Main {
    private static int N, M;
    private static int[] combinations, items;
    private static boolean[] visited;
    private static StringBuilder sb = new StringBuilder();
    private static void dfs(int index, int depth) {
        // 종료 조건
        if (depth == M) {
            for (int i = 0; i < M; i++) {
                sb.append(combinations[i]).append(" ");
            }
            sb.append("\n");
            return;
        }
        for (int i = index; i < N; i++) {
            combinations[depth] = items[i];
            dfs(i,depth + 1);
        }
    }
    public static void main(String[] args) throws IOException {
        StringTokenizer st;

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        items = new int[N];
        combinations = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            items[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(items);
        dfs(0,0);
        System.out.println(sb.toString());
    }
}

N과 M (9)

+ 중복 수열은 출력하지 않는다.

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

public class Main {
    private static int N, M;
    private static int[] combinations, items;
    private static boolean[] visited;
    private static StringBuilder sb = new StringBuilder();
    private static void dfs(int depth) {
        // 종료 조건
        if (depth == M) {
            for (int i = 0; i < M; i++) {
                sb.append(combinations[i]).append(" ");
            }
            sb.append("\n");
            return;
        }
        int prevNumber = -1;
        for (int i = 0; i < N; i++) {
            if (prevNumber != items[i] && !visited[i]) {
                combinations[depth] = items[i];
                prevNumber = items[i];
                visited[i] = true;
                dfs(depth + 1);
                visited[i] = false;
            }
        }
    }
    public static void main(String[] args) throws IOException {
        StringTokenizer st;

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        items = new int[N];
        combinations = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            items[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(items);
        visited = new boolean[N];
        dfs(0);
        System.out.println(sb.toString());
    }
}

N과 M (10)

+ 같은 수를 여러 번 골라도 된다.

+ 중복 수열은 출력하지 않는다.

+ 수열은 오름차순이어야 한다. (자기 자신보다 작은 숫자를 그 다음 숫자로 만들어서는 안 된다.)

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

public class Main {
    private static int N, M;
    private static int[] combinations, items;
    private static boolean[] visited;
    private static StringBuilder sb = new StringBuilder();
    private static void dfs(int index, int depth) {
        // 종료 조건
        if (depth == M) {
            for (int i = 0; i < M; i++) {
                sb.append(combinations[i]).append(" ");
            }
            sb.append("\n");
            return;
        }
        int prevNumber = -1;
        for (int i = index; i < N; i++) {
            if (prevNumber != items[i] && !visited[i]) {
                combinations[depth] = items[i];
                prevNumber = items[i];
                visited[i] = true;
                dfs(i, depth + 1);
                visited[i] = false;
            }
        }
    }
    public static void main(String[] args) throws IOException {
        StringTokenizer st;

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        items = new int[N];
        combinations = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            items[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(items);
        visited = new boolean[N];
        dfs(0, 0);
        System.out.println(sb.toString());
    }
}

N과 M (11)

+ 같은 수를 여러 번 골라도 된다.

+ 중복 수열은 출력하지 않는다.

+ 같은 숫자를 여러 번 골라도 된다.

package org.example;

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

public class Main {
    private static int N, M;
    private static int[] combinations, items;
    private static StringBuilder sb = new StringBuilder();
    private static void dfs(int index, int depth) {
        // 종료 조건
        if (depth == M) {
            for (int i = 0; i < M; i++) {
                sb.append(combinations[i]).append(" ");
            }
            sb.append("\n");
            return;
        }
        int prevNumber = -1;
        for (int i = 0; i < N; i++) {
            if (prevNumber != items[i]) {
                combinations[depth] = items[i];
                prevNumber = items[i];
                dfs(i, depth + 1);
            }
        }
    }
    public static void main(String[] args) throws IOException {
        StringTokenizer st;

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        items = new int[N];
        combinations = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            items[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(items);
        dfs(0, 0);
        System.out.println(sb.toString());
    }
}

N과 M (12)

+ 같은 수를 여러 번 골라도 된다.

+ 중복 수열은 출력하지 않는다.

+ 수열은 오름차순이어야 한다. (자기 자신보다 작은 숫자를 그 다음 숫자로 만들어서는 안 된다.)

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

public class Main {
    private static int N, M;
    private static int[] combinations, items;
    private static List<Integer> itemsDistinct;
    private static StringBuilder sb = new StringBuilder();
    private static void dfs(int index, int depth) {
        // 종료 조건
        if (depth == M) {
            for (int i = 0; i < M; i++) {
                sb.append(combinations[i]).append(" ");
            }
            sb.append("\n");
            return;
        }
        int prevNumber = -1;
        for (int i = index; i < N; i++) {
            if (prevNumber != items[i]) {
                combinations[depth] = items[i];
                prevNumber = items[i];
                dfs(i, depth + 1);
            }
        }
    }
    public static void main(String[] args) throws IOException {
        StringTokenizer st;

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        items = new int[N];
        combinations = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            items[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(items);
        dfs(0, 0);
        System.out.println(sb.toString());
    }
}