[Java] 백준 N과 M 1~6

Lee GaEun·2025년 1월 24일

[Java] 알고리즘

목록 보기

50/93

N과 M (1)

#1

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

class Main {
    static boolean[] visited;
    static int N;
    static int M;
    static LinkedList<Integer> answer = new LinkedList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        visited = new boolean[N];
        answer.add(0);
        printSeq(M, 0);

        System.out.println();
    }

    static void printSeq(int m, int j) {
        if(m==0) {
            for(int i=1; i<=M; i++) {
                System.out.print(answer.get(i)+" ");
            }
            System.out.println();
            answer.removeLast();
            return;
        }

        for(int i=0; i<N; i++) {
            if(!visited[i]) {
                answer.add(i+1);
                visited[i] = true;
                printSeq(m-1, i);
            }
        }
        for(int i=j; i<=M; i++) {
            visited[i] = false;
        }
        answer.removeLast();
    }
}

빽트래킹은 뒤로 돌아가는 게 어려움..

#2

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

class Main {
    static boolean[] visited;
    static int N;
    static int M;
    static LinkedList<Integer> answer = new LinkedList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        visited = new boolean[N];
        answer.add(0);
        printSeq(M);

        System.out.println();
    }

    static void printSeq(int m) {
        if(m==0) {
            for(int i=1; i<=M; i++) {
                System.out.print(answer.get(i)+" ");
            }
            System.out.println();
            answer.removeLast();
            return;
        }

        for(int i=0; i<N; i++) {
            if(!visited[i]) {
                answer.add(i+1);
                visited[i] = true;
                printSeq(m-1);
                visited[i] = false;
            }
        }
        answer.removeLast();
    }
}

visited의 요소를 false로 돌려주는 타이밍 보는 게 좀 걸림..
암튼 성공!

#3

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

class Main {
    static boolean[] visited;
    static int N;
    static int M;
    static int[] answer;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        answer = new int[M];
        visited = new boolean[N];
        printSeq(0);
    }

    static void printSeq(int target) {
        if(target == M) {
            for(int i=0; i<M; i++) {
                System.out.print(answer[i]+" ");
            }
            System.out.println();
            return;
        }

        for(int i=0; i<N; i++) {
            if(!visited[i]) {
                answer[target] = i+1;
                visited[i] = true;
                printSeq(target+1);
                visited[i] = false;
            }
        }
    }
}

코드가 더러워서 N과 M (2) 풀기가 힘듦..
그래서 answer LinkedList 말고 배열로 바꿔줌

15650 N과 M (2) 문제 링크

N과 M (2)

#1

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

class Main {
    static boolean[] visited;
    static int N;
    static int M;
    static int[] answer;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        answer = new int[M];
        visited = new boolean[N];
        printSeq(0, 0);
    }

    static void printSeq(int target, int level) {
        if(target == M) {
            for(int i=0; i<M; i++) {
                System.out.print(answer[i]+" ");
            }
            System.out.println();
            return;
        }

        for(int i=level; i<N; i++) {
            if(!visited[i]) {
                answer[target] = i+1;
                visited[i] = true;
                printSeq(target+1, i);
                visited[i] = false;
            }
        }
    }
}

N과 M (1) 문제에서 visited[i] = false;의 위치만 옮기면 풀릴 줄 알고 여기저기 옮겨보고 고민하느라 오래 걸림
백트래킹 문제는 값을 되돌리는 부분을 지정하는 게 어려움
탐색하는 for문의 시작을 0부터가 아닌 level부터로 해서 문제를 해결
- N과 M (1) 문제와 똑같은데 순서 없는 배열을 뽑아내는 걸로 해서
- 앞의 수보다 뒤의 수가 더 작은 경우가 없기 때문

15651 N과 M (3) 문제 링크

N과 M (3)

#1

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

class Main {
    static int N;
    static int M;
    static int[] answer;
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    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());

        answer = new int[M];
        printSeq(0);
        bw.flush();
        bw.close();
    }

    static void printSeq(int target) throws IOException {
        if(target == M) {
            for(int i=0; i<M; i++) {
                bw.write(answer[i]+" ");
            }
            bw.write("\n");
            return;
        }

        for(int i=0; i<N; i++) {
            answer[target] = i+1;
            printSeq(target+1);
        }
    }
}

이게 백트래킹인가..? N과 M (2) 문제에서 백트래킹 요소만 빼면 답임..
시간초과 나서 System.out.println();출력만 bw.write();출력으로 바꿈..

15652 N과 M (4) 문제 링크

N과 M (4)

#1

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

class Main {
    static int N;
    static int M;
    static int[] answer;
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    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());

        answer = new int[M];
        printSeq(0, 0);
        bw.flush();
        bw.close();
    }

    static void printSeq(int target, int level) throws IOException {
        if(target == M) {
            for(int i=0; i<M; i++) {
                bw.write(answer[i]+" ");
            }
            bw.write("\n");
            return;
        }

        for(int i=level; i<N; i++) {
            answer[target] = i+1;
            printSeq(target+1, i);
        }
    }
}

성공!

15654 N과 M (5) 문제 링크

N과 M (5)

#1

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

class Main {
    static int N;
    static int M;
    static int[] answer;
    static boolean[] visited;
    static int[] arr;
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    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());

        st = new StringTokenizer(br.readLine());
        arr = new int[N];
        for(int i=0; i<N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr);

        visited = new boolean[N];
        answer = new int[M];
        printSeq(0);
        bw.flush();
        bw.close();
    }

    static void printSeq(int target) throws IOException {
        if(target == M) {
            for(int i=0; i<M; i++) {
                bw.write(answer[i]+" ");
            }
            bw.write("\n");
            return;
        }

        for(int i=0; i<N; i++) {
            if(!visited[i]) {
                answer[target] = arr[i];
                visited[i] = true;
                printSeq(target + 1);
                visited[i] = false;
            }
        }
    }
}

성공!

15655 N과 M (6) 문제 링크

N과 M (6)

#1

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

class Main {
    static int N;
    static int M;
    static int[] answer;
    static boolean[] visited;
    static int[] arr;
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    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());

        st = new StringTokenizer(br.readLine());
        arr = new int[N];
        for(int i=0; i<N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr);

        visited = new boolean[N];
        answer = new int[M];
        printSeq(0, 0);
        bw.flush();
        bw.close();
    }

    static void printSeq(int target, int level) throws IOException {
        if(target == M) {
            for(int i=0; i<M; i++) {
                bw.write(answer[i]+" ");
            }
            bw.write("\n");
            return;
        }

        for(int i=level; i<N; i++) {
            if(!visited[i]) {
                answer[target] = arr[i];
                visited[i] = true;
                printSeq(target + 1, i);
                visited[i] = false;
            }
        }
    }
}