Jun's Development Journey

[BOJ] N과 M(백트래킹 입문 4문제) 본문

BOJ/단계별로 풀어보기

[BOJ] N과 M(백트래킹 입문 4문제)

J_Jayce 2021. 4. 1. 13:12

문제1

www.acmicpc.net/problem/15649

 

15649번: N과 M (1)

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해

www.acmicpc.net

풀이

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


public class BOJ_15650 {
    static int[] arr;
    static int[] tmp;
    static boolean[] visited;
    static StringBuilder sb;
    static void backtracking(int st,int depth, int N, int std){
        if(depth == std){
            for(int n : tmp)
                sb.append(n+" ");
            sb.append("\n");
            return;
        }
        for(int i=0;i<N;i++){
            if(!visited[i]){
                tmp[depth] = arr[i];
                visited[i] = true;
                backtracking(i+1,depth+1,N,std);
                visited[i] = false;
            }
        }
    }
    public static void main(String[] args) throws IOException {
        // TODO Auto-generated method stub
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N,M;
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        sb = new StringBuilder();
        arr = new int[N];
        tmp = new int[M];
        visited = new boolean[N];
        for(int i=1;i<=N;i++)
            arr[i-1] = i;

        backtracking(0,0,N,M);
        System.out.println(sb);
    }
}

문제2

www.acmicpc.net/problem/15650

 

15650번: N과 M (2)

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해

www.acmicpc.net

풀이

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


public class BOJ_15650 {
    static int[] arr;
    static int[] tmp;
    static boolean[] visited;
    static StringBuilder sb;
    static void backtracking(int st,int depth, int N, int std){
        if(depth == std){
            for(int n : tmp)
                sb.append(n+" ");
            sb.append("\n");
            return;
        }
        for(int i=st;i<N;i++){
            if(!visited[i]){
                tmp[depth] = arr[i];
                visited[i] = true;
                backtracking(i+1,depth+1,N,std);
                visited[i] = false;
            }
        }
    }
    public static void main(String[] args) throws IOException {
        // TODO Auto-generated method stub
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N,M;
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        sb = new StringBuilder();
        arr = new int[N];
        tmp = new int[M];
        visited = new boolean[N];
        for(int i=1;i<=N;i++)
            arr[i-1] = i;

        backtracking(0,0,N,M);
        System.out.println(sb);
    }
}

문제3

www.acmicpc.net/problem/15651

 

15651번: N과 M (3)

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해

www.acmicpc.net

풀이

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


public class BOJ_15650 {
    static int[] arr;
    static int[] tmp;
    static StringBuilder sb;
    static void backtracking(int st,int depth, int N, int std){
        if(depth == std){
            for(int n : tmp)
                sb.append(n+" ");
            sb.append("\n");
            return;
        }
        for(int i=0;i<N;i++){
            tmp[depth] = arr[i];
            backtracking(i+1,depth+1,N,std);
        }
    }
    public static void main(String[] args) throws IOException {
        // TODO Auto-generated method stub
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N,M;
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        sb = new StringBuilder();
        arr = new int[N];
        tmp = new int[M];
        for(int i=1;i<=N;i++)
            arr[i-1] = i;

        backtracking(0,0,N,M);
        System.out.println(sb);
    }
}

문제4

www.acmicpc.net/problem/15652

 

15652번: N과 M (4)

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해

www.acmicpc.net

풀이

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


public class BOJ_15650 {
    static int[] tmp;
    static StringBuilder sb;
    static void backtracking(int st,int depth, int N, int std){
        if(depth == std){
            for(int n : tmp)
                sb.append(n+" ");
            sb.append("\n");
            return;
        }
        for(int i=st;i<=N;i++){
            tmp[depth] = i;
            backtracking(i,depth+1,N,std);
        }
    }
    public static void main(String[] args) throws IOException {
        // TODO Auto-generated method stub
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N,M;
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        sb = new StringBuilder();
        tmp = new int[M];

        backtracking(1,0,N,M);
        System.out.println(sb);
    }
}

'BOJ > 단계별로 풀어보기' 카테고리의 다른 글

[BOJ] 14889 스타트와 링크(백트래킹)  (0) 2021.04.01
[BOJ] 9663 N-Queen(Backtracking 대표 문제)  (0) 2021.04.01
[BOJ] 1065번 한수  (0) 2021.03.23
[BOJ] 4673번 셀프 넘버  (0) 2021.03.23
[BOJ] 입출력과 사칙연산 - 10171번 고양이, 10172번 강아지  (0) 2021.03.23
'BOJ/단계별로 풀어보기' Related Articles more