[알고리즘 문제풀이] 백준 - N과M(2) / JAVA(자바)

목차

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

15650번: N과 M (2)

 

선행학습: 재귀

 

/*
   1~N중에서 M개를 고른 수열
   오름차순 정렬이고 중복 없으므로
   visited 개념으로 리스트를 만들어서 사용했으면 넘어갈것
   그리고 다음 고른 숫자가 기존에 고른것보다 작으면 넘어갈것

*/


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

public class Main {

    public static int n;
    public static int m;
    
    // 숫자 배열
    public static int[] arr;

    // 선택숫자 배열
    public static int[] choice;


    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());
        
        //숫자 배열 길이 생성
        arr = new int[n+1];

        // 선택담을 배열 생성
        choice = new int[m];

        solve(0);
    }

    public static void solve(int stage){

        // 다 골랐을때
        if(stage == m){
            //선택 배열 돌면서 출력
            for(int idx = 0; idx < m; idx++){
                System.out.print(choice[idx] + " ");
                }
            System.out.println();
            return;
        }

        // 숫자를 돌면서 고르기
        for(int i =1; i <= n; i++){
            // 고르지 않은 숫자일때
            if(arr[i] == 0){
                // 한개이상의 숫자를 골랐다면 현재 고른 숫자가
                // 기존의 고른 숫자보다 커야함 크지않으면 다음숫자확인
                if(stage > 0 && i < choice[stage-1]) continue;

                // 고른숫자 담기
                choice[stage] = i;
                // 숫자 사용한것으로 표기
                arr[i] = 1;
                // 다음숫자 고르러 가기
                solve(stage+1);
                // 초기화
                arr[i] = 0;
            }
        }
        return;
    }
}

 

2) pnum을 이용한 풀이

 

/*
    1. n과 m 을 받기

    2. n까지의 자연수 중에서 m개의 숫자를 고르기

    3. 1~n까지의 숫자 중에서 고를 때마다, 다시 함수를 불러서 다음 숫자를 고를 것.
    3-1) 함수에서 숫자를 고를땐, 골랐던것은 고르면 안됨.
    3-2) 오름차순이어야함.

    4. 다 골랐을때, 고른 숫자를 출력할 것.
*/

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

public class Test {

    public static int n, m;
    public static boolean[] visited;
    public static int[] choice;
    public static BufferedWriter bw;
    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());

        // 현재 숫자를 사용했었는지 체크하기위한 배열
        visited = new boolean[n+1];
        // 고른 숫자를 저장해두기 위한 배열
        choice = new int[m];

        solve(0,0); // 숫자를 고를 함수
    }

    // 숫자를 고를 함수(stage: 숫자를 고른 갯수, pnum: 과거에 고른 숫자)
    public static void solve(int stage, int pnum){

        // 종료조건(m 개의 숫자를 다 골랐을때)
        if(stage == m){
            // 고른 숫자들을 출력
            for(int j = 0; j < m; j++){
                System.out.print(choice[j] + " ");
            }
            System.out.println();
            return;
        }

        // n까지의 숫자를 돌면서 고를 것(과거에 고른 숫자보다 1만큼 큰것부터 확인)
        for(int i = pnum +1; i <= n; i++){
            // 현재 숫자를 안골랐을때 고를 것.
            if(visited[i] == false){
                // 배열에 고른 숫자 담아두기
                choice[stage] = i;
                // 현재 숫자를 고른것으로 체크
                visited[i] = true;
                // 다음 숫자를 고르러 가기(pnum 현재 고른 숫자도 같이 넘기기)
                solve(stage+1,i);
                // 초기화작업(현재 숫자를 다시 고를 수 있게 하기 위해)
                visited[i] = false;
            }
        }
    }
}