190326 BOJ (15649,15650) N과 M (1)(2)

2019-03-26

15649, 15650. N과 M(1)(2)

문제

출처

출처2

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

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

입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

출력

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

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

문제 풀이 - 15649

  • 1~N중 M개를 순서대로 뽑는다 : 순열
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

class Main {
    static void dfs(int cnt){
        if(cnt==M){
            for(int i=0;i<res.size();i++){
                System.out.print(res.get(i)+" ");
            }
            System.out.println();
            return;
        }

        for(int i=1;i<=N;i++){
            // 1~N까지 수 중 뽑은 수는 res 리스트에 들어간다.
            if(visited[i]) continue;
            visited[i]=true;
            res.add(i);
            dfs(cnt+1);
            visited[i]=false;
            res.remove(res.size()-1);
        }
    }
    static int N,M;
    static boolean[] visited;
    static ArrayList<Integer> res=new ArrayList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        String[] tmp=br.readLine().split(" ");
        N=Integer.parseInt(tmp[0]);
        M=Integer.parseInt(tmp[1]);
        visited=new boolean[N+1];

        dfs(0);
    }
}

문제 풀이 - 15650

  • 1~N에서 순서 상관없이 M개 뽑기: 조합
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

class Main {
    static void dfs(int idx,int cnt){
        if(cnt==M){

            for(int i=0;i<res.size();i++){
                System.out.print(res.get(i)+" ");
            }
            System.out.println();
            return;
        }

        for(int i=idx;i<=N;i++){
            // idx부터 시작함에 주의. 
            // -> 오름차순으로 뽑아야 하므로, 이미 뽑은 idx보다 작은 것들에 대해서는 탐색X
            if(visited[i]) continue;
            visited[i]=true;
            res.add(i);
            dfs(i,cnt+1);
            visited[i]=false;
            res.remove(res.size()-1);
        }
    }
    static int N,M;
    static boolean[] visited;
    static ArrayList<Integer> res=new ArrayList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        String[] tmp=br.readLine().split(" ");
        N=Integer.parseInt(tmp[0]);
        M=Integer.parseInt(tmp[1]);
        visited=new boolean[N+1];

        dfs(1,0);
    }
}
  • 두 방법의 차이를 알자