[백준] N과M(1, 2, 3, 4) / 백트래킹

 

Sliver

 

 

문제

 

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

 

---

 

조건 1

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

 

 

풀이

import java.util.*;

public class Main {
    static boolean[] visited;
    static int[] result;
    static StringBuilder sb;
    static int N, M;
    
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        sb = new StringBuilder();
        N = sc.nextInt();
        M = sc.nextInt();
    
        result = new int[M];
        visited = new boolean[N];
        dfs(0);
        sc.close();
    }

    public static void dfs(int count){
        if(count == M){
            print();
            return;
        }

        for(int i=0; i<N; i++){
            if(!visited[i]){
                visited[i] = true;
                result[count] = i+1;
                dfs(count+1);
                visited[i] = false;
            }
        }        
    }

    public static void print(){
        for(int i=0; i<M; i++){
            System.out.print(result[i] + " ");
        }
        System.out.println();
    }

}

 

중복을 없애기 위해 visited 배열 만들어 방문하였음을(이미 선택했음을) 체크할 수 있도록 하였다. 

 

 

---

 

 

조건2

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
• 고른 수열은 오름차순이어야 한다.

 

풀이

 

import java.util.*;

public class Main {
    static int[] result;
    static int N, M;
    
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
    
        result = new int[M];
        dfs(0,0);
        sc.close();
    }

    public static void dfs(int depth, int start){
        if(depth == M){
            print();
            return;
        }
        for(int i=start; i<N; i++){
            result[depth] = i+1;
            dfs(depth+1, i+1);
        }
    }

    public static void print(){
        for(int i=0; i<result.length; i++){
            System.out.print(result[i] + " ");
        }
        System.out.println();
    }

}

 

 

 

 

---

 

조건3

• 1부터 N까지 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.

 

풀이

 

import java.util.*;

class Main {

    static int[] result;
    static int N, M;
    static StringBuilder sb;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        sb = new StringBuilder();
        N = sc.nextInt();
        M = sc.nextInt();
        result = new int[M];
        dfs(0);
        System.out.print(sb);
        sc.close();
    }

    public static void dfs(int index){
        if(index == M){
            print();
            return;
        }
        for(int i=0; i<N; i++){
            result[index] = i+1;
            dfs(index+1);
        }
    }

    public static void print(){
        for(int i=0; i<result.length; i++){
            sb.append(result[i] + " ") ;
        }
        sb.append("\n");
    }
}

 

 

 

---

 

조건4

• 1부터 N까지 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.
• 고른 수열은 비내림차순이어야 한다.
  • 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.

 

풀이

 

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


class Main {
    static int N, M;
    static int[] result;
    static StringBuilder sb;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        sb = new StringBuilder();
        N = sc.nextInt();
        M = sc.nextInt();
        result = new int[M];
        dfs(0, 0);
        System.out.println(sb);
        sc.close();
    }

    public static void dfs(int depth, int start){
        if(depth == M){
            print();
            return;
        }

        for(int i=start; i<N; i++){
            result[depth] = i+1;
            dfs(depth+1,i);
        }
        
    }
    public static void print(){
        for(int i=0; i<result.length; i++){
            sb.append(result[i] + " ");
        }
        sb.append("\n");
    }
    
}

 

 

 

 

---

 

https://www.acmicpc.net/problem/15649

https://www.acmicpc.net/problem/15650

https://www.acmicpc.net/problem/15651

https://www.acmicpc.net/problem/15652