[백준 문제집] N과 M 시리즈

본문 바로가기

Notice

Recent Posts

Recent Comments

Link

Tags more

Archives

Today

Total

관리 메뉴

Dev.baelanche

[백준 문제집] N과 M 시리즈 본문

Data Structure & Algorithm/PS - JAVA

[백준 문제집] N과 M 시리즈

baelanche 2019. 6. 19. 21:19

문제 전문 이미지는 생략하도록 하겠다.

N과 M 시리즈는 모~~두 백트래킹 문제로 시리즈별로 난이도 차이는 거의 없다.

백트래킹을 모른다면 간단히 공부하고 오거나 천재라면 필자의 빈약한... 소스를 보고 이해하면 되겠다.

15649번 : N과 M(1)

중복없는 수열을 뽑아야 하므로 방문배열을 만들어 주어야 한다.

낮은 번호부터 순서대로 진행하며 배열체크만 해주면 된다.

public class Main {
    
    static int n;
    static int m;
    static boolean visited[];
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        visited = new boolean[n+1];
        
        dfs(0, "");
    }
    
    public static void dfs(int len, String str) {
        if(len == m) {
            System.out.println(str);
            return;
        }
        
        for(int i=1; i<=n; i++) {
            if(!visited[i]) {
                visited[i] = true;
                dfs(len + 1, str + i + " ");
                visited[i] = false;
            }
        }
    }
}

15650번 : N과 M(2)

오름차순으로, n번째 수 x 뒤에는 x 보다 큰 수만 와야 한다.

중복된 수가 오지 않으므로 방문배열은 필요없다.

public class Main {
    
    static int n;
    static int m;
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        
        dfs(0, 0, "");
    }
    
    public static void dfs(int idx, int len, String str) {
        if(len == m) {
            System.out.println(str);
            return;
        }
        
        for(int i=1; i<=n; i++)
            if(i > idx)
                dfs(i, len + 1, str + i + " ");
    }
}

15651번 : N과 M(3)

앞서 진행했던 것과 동일하나 조건없이 모든 경우를 다 출력해주면 된다.

public class Main {
    
    static int n;
    static int m;
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        
        dfs(0, "");
    }
    
    public static void dfs(int len, String str) {
        if(len == m) {
            System.out.println(str);
            return;
        }
        
        for(int i=1; i<=n; i++)
            dfs(len + 1, str + i + " ");
    }
}

15652번 : N과 M(4)

수열의 n번째 자리 수 보다 n+1번째 자리의 수가 같거나 크면 된다.

public class Main {
    
    static int n;
    static int m;
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        
        dfs(0, 0, "");
    }
    
    public static void dfs(int idx, int len, String str) {
        if(len == m) {
            System.out.println(str);
            return;
        }
        
        for(int i=1; i<=n; i++)
            if(i >= idx)
                dfs(i, len + 1, str + i + " ");
    }
}

15654번 : N과 M(5)

입력받은 수들은 오름차순으로 정렬하며

방문 배열을 만들어 중복된 수가 없게 한다.

public class Main {
    
    static int n;
    static int m;
    static int a[];
    static boolean visited[];
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        visited = new boolean[10001];
        a = new int[n];
        
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<n; i++) a[i] = Integer.parseInt(st.nextToken());
        
        Arrays.sort(a);
        dfs(0, "");
    }
    
    public static void dfs(int len, String str) {
        if(len == m) {
            System.out.println(str);
            return;
        }
        
        for(int i=0; i<n; i++) {
            if(!visited[a[i]]) {
                visited[a[i]] = true;
                dfs(len + 1, str + a[i] + " ");
                visited[a[i]] = false;
            }
        }
    }
}

15655번 : N과 M(6)

그렇다. n번째 수보다 n+1번째 수가 크면 된다.

public class Main {
    
    static int n;
    static int m;
    static int a[];
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        a = new int[n];
        
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<n; i++) a[i] = Integer.parseInt(st.nextToken());
        
        Arrays.sort(a);
        dfs(0, 0, "");
    }
    
    public static void dfs(int idx, int len, String str) {
        if(len == m) {
            System.out.println(str);
            return;
        }
        
        for(int i=0; i<n; i++)
            if(a[i] > idx)
                dfs(a[i], len + 1, str + a[i] + " ");
    }
}

15656번 : N과 M(7)

오름차순 정렬한 배열의 모든 경우를 출력하면 된다.

public class Main {
    
    static int n;
    static int m;
    static int a[];
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        a = new int[n];
        
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<n; i++) a[i] = Integer.parseInt(st.nextToken());
        
        Arrays.sort(a);
        dfs(0, "");
    }
    
    public static void dfs(int len, String str) {
        if(len == m) {
            System.out.println(str);
            return;
        }
        
        for(int i=0; i<n; i++)
            dfs(len + 1, str + a[i] + " ");
    }
}

15657번 : N과 M(8)

n번째 수보다 n+1번째 수가 같거나 크다.

public class Main {
    
    static int n;
    static int m;
    static int a[];
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        a = new int[n];
        
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<n; i++) a[i] = Integer.parseInt(st.nextToken());
        
        Arrays.sort(a);
        dfs(0, 0, "");
    }
    
    public static void dfs(int idx, int len, String str) {
        if(len == m) {
            System.out.println(str);
            return;
        }
        
        for(int i=0; i<n; i++)
            if(a[i] >= idx)
                dfs(a[i], len + 1, str + a[i] + " ");
    }
}

15663번 : N과 M(9)

N과 M 시리즈의 보스 문제다. (보스 치고는 약하다...)

수열은 중복되면 안되므로 Set 으로 구현했다. 다른 방법을 알고 있다면 그 방법을 사용해도 무방하다.

자바의 TreeSet을 사용하였고 트리 특성상 정렬 상태를 유지하므로 따로 정렬을 해줄 필요가 없다.

두번째 예제 {9, 7, 9, 1}의 경우 리스트에는 9를 한개만 담지만 출력에는 9 9 가 있는걸 알 수 있다.

그래서 방문 배열을 정수형으로 만들어 true, false 가 아닌 정수의 개수를 담아서 사용했다.

소스를 보면 아주아주 쉽게 이해할 수 있다.

public class Main {
    
    static int n;
    static int m;
    static ArrayList<Integer> a;
    static int visited[] = new int[10001];
    
    public static void main(String[] args) throws Exception {
        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());
        Set<Integer> s = new TreeSet<Integer>();
        for(int i=0; i<n; i++) {
            int t = Integer.parseInt(st.nextToken());
            s.add(t);
            visited[t]++;
        }
        
        a = new ArrayList<Integer>(s);
        dfs(0, "");
    }
    
    public static void dfs(int len, String str) {
        if(len == m) {
            System.out.println(str);
            return;
        }
        
        for(int i=0; i<a.size(); i++) {
            if(visited[a.get(i)] > 0) {
                visited[a.get(i)]--;
                dfs(len + 1, str + a.get(i) + " ");
                visited[a.get(i)]++;
            }
        }
    }
}

15664번 : N과 M(10)

앞으로의 문제들은 N과 M(9) 문제를 기반으로 한 두 줄씩 바꿔주면 된다.

중복이 없고 n번째 수보다 n+1번째 수가 같거나 크다.

public class Main {
    
    static int n;
    static int m;
    static ArrayList<Integer> a;
    static int visited[] = new int[10001];
    
    public static void main(String[] args) throws Exception {
        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());
        Set<Integer> s = new TreeSet<Integer>();
        for(int i=0; i<n; i++) {
            int t = Integer.parseInt(st.nextToken());
            s.add(t);
            visited[t]++;
        }
        
        a = new ArrayList<Integer>(s);
        dfs(0, 0, "");
    }
    
    public static void dfs(int idx, int len, String str) {
        if(len == m) {
            System.out.println(str);
            return;
        }
        
        for(int i=0; i<a.size(); i++) {
            if(a.get(i) >= idx) {
                if(visited[a.get(i)] > 0) {
                    visited[a.get(i)]--;
                    dfs(a.get(i), len + 1, str + a.get(i) + " ");
                    visited[a.get(i)]++;
                }
            }
        }
    }
}

15665번 : N과 M(11)

N과 M(9)를 바탕으로 구현한 소스에서 조건없이 모두 출력해주면 된다.

public class Main {
    
    static int n;
    static int m;
    static ArrayList<Integer> a;
    
    public static void main(String[] args) throws Exception {
        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());
        Set<Integer> s = new TreeSet<Integer>();
        for(int i=0; i<n; i++) {
            int t = Integer.parseInt(st.nextToken());
            s.add(t);
        }
        
        a = new ArrayList<Integer>(s);
        dfs(0, "");
    }
    
    public static void dfs(int len, String str) {
        if(len == m) {
            System.out.println(str);
            return;
        }
        
        for(int i=0; i<a.size(); i++)
            dfs(len + 1, str + a.get(i) + " ");
        
    }
}

15666번 : N과 M(12)

n번째 수보다 n+1번째 수가 같거나 크기만 하면 된다.

public class Main {
    
    static int n;
    static int m;
    static ArrayList<Integer> a;
    
    public static void main(String[] args) throws Exception {
        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());
        Set<Integer> s = new TreeSet<Integer>();
        for(int i=0; i<n; i++) {
            int t = Integer.parseInt(st.nextToken());
            s.add(t);
        }
        
        a = new ArrayList<Integer>(s);
        
        dfs(0, 0, "");
    }
    
    public static void dfs(int idx, int len, String str) {
        if(len == m) {
            System.out.println(str);
            return;
        }
        
        for(int i=0; i<a.size(); i++)
            if(a.get(i) >= idx)
                dfs(a.get(i), len + 1, str + a.get(i) + " ");
    }
}

두번째 문제집 클리어다!

다 푸는데 한시간도 안걸린 것 같아 뿌듯함은 별로 없다...

저작자표시

'Data Structure & Algorithm > PS - JAVA' 카테고리의 다른 글

[백준 16234] 인구 이동 (0)	2019.06.20
[백준 14889] 스타트와 링크 (0)	2019.06.20
[백준 10997] 별 찍기 - 22 (0)	2019.06.19
[백준 10993] 별 찍기 - 18 (0)	2019.06.18
[백준 10757] 큰 수 A+B (0)	2019.06.18

'Data Structure & Algorithm/PS - JAVA' Related Articles

more

Comments

티스토리툴바