백준 [N15650 - N과 M(2)]

백트래킹의 N과M시리즈 2번째 문제를 풀어보았다.

N과M시리즈에서 사용할 bt()함수는 비슷하다. 문제에 따라 매개변수, 반복문 내 로직이 달라진다.

일단, 기본 포맷은 아래와 같다.

public static void bt(int cnt){
   //cnt 즉, 깊이가 m과 같아질때는 출력을 한다.
   if(cnt == m){
    //출력문
    return;
   }
   
   for(/*...*/){
     //반복문
  }
}

 

 

N과 M(1),(2) 문제

 

이전에 풀었던 N과M(1) 문제와 차이점은 고른 수열이 오름차순이여야 한다는 점 한가지이다.

N = 4, M=2 입출력 예제를 보면 아래와 같은 차이를 보인다. 

 

 

 

 

 

 

 

 

 

 

 

 

 

N과 M(1)

N과 M(2)

 

[알고리즘] - 백준 [N15649 - N과 M(1)]

백준 [N15649 - N과 M(1)]

N과 M(1) bt()함수와 달라진 점은

첫번째로 고른수보다 큰 수만 고를 수 있도록 기준을 잡아줄 변수(start)를 사용함으로써
방문배열이 필요없어진 차이점이 생긴다

N과 M(1)에서 방문배열이 필요했었던 이유는 for문이 1부터 N까지 돌면서 방문여부(숫자를 고른여부)를 확인해 중복없이 수를 골라야 하기 때문이다.

하지만,

N과 M(2)에서는 for문이 start(기준점)부터 N까지 돌면서 start보다 큰 수만 고르면 되기 때문에 방문여부를 확인하는 배열이 필요 없어진다.

 

전체소스

public class Main {
    private static int n,m;
    private static int[] arr;
    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[m];
        bt(1, 0);
    }

    public static void bt(int start, int cnt){
        if(cnt == m){
            for(int i : arr) System.out.print(i+" ");
            System.out.println();
            return;
        }

        for(int i=start;i<=n;i++){
                arr[cnt] = i;
                bt(i+1, cnt+1);
        }
    }
}

.