[BOJ] 백준 15650 N과 M (2)

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

 Input 
4 2

 Output 

1 2

1 3

1 4

2 3

2 4

3 4

중복 없는 조합을 구현하는 문제이다.

조합의 경우는 선택 여부로 구현할 수 있다.

 

arr = [1, 2, 3, 4]

[1  3]; 1을 선택한 후, 3을 선택한 경우

[1  4]; 1을 선택한 후, 4를 선택한 경우

[2  1]; 처음 1을 선택하지 않고, 2를 선택한 경우

[1  2]; 1을 선택한 후, 2를 선택한 경우

(이하 생략)

 

▶ 순열과 조합 (백준 N과 M 시리즈) 

순열과 조합 (백준 N과 M 시리즈)

 

활용 문제

- [SWEA] 3421 수제 버거 장인  (중복 없는 조합)

---

C / C++

#include <stdio.h>

const int MAX_N = 8 + 2;
int N, M, ans[MAX_N];
bool visited[MAX_N];

void DFS(int idx, int depth) {
    if (depth == M) {
        for (int i = 0; i < M; ++i) {
            printf("%d ", ans[i]);
        }
        printf("\n");
        return;
    }
    for (int i = idx; i < N; ++i) {
        if (visited[i]) continue;
        visited[i] = true;
        ans[depth] = i + 1;
        DFS(i, depth + 1);
        visited[i] = false;
        ans[depth] = 0;
    }
}

int main() {
    // freopen("input.txt", "r", stdin);
    scanf("%d %d", &N, &M);
    DFS(0, 0);
}

 

Java

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
 
public class Main {
      
    static int[] arr;
    static int N, M;
     
    public static void main(String[] args) {
        Scanner sc = new  Scanner(System.in);
         
        N = Integer.parseInt(sc.next());
        M = Integer.parseInt(sc.next());
         
        arr = new int[N];
        for(int i=0; i < N; i++) {
            arr[i] = i+1;
        }
        // 뽑힌 원소를 알아내기 위한 배열
        List<Integer> output = new ArrayList<>();
         
        // 원소를 뽑기 시작할 배열상의 위치와
        // 조합으로 뽑힌 원소들을 저장할 리스트를 인자로  전달.
        combination(0, output);
    }
     private static void combination(int idx,  List<Integer> output) {
           
          // 이미 원하는 길이의 조합을 만족했으면 출력하고  종료  
          if(output.size() >= M) {
            // 지금까지 방문한(뽑힌) 원소를 출력한다.
            for(int i=0; i<M; i++) {
              System.out.print(output.get(i) + " ");
            }
            System.out.println();
            return;
          }
           
          // 더 이상 뽑을 원소가 없다면 길이를 만족하지 못하는 조합을 하고 있었던 것이다.
          if(idx >= N) {
              return;
          }
           
          // 중복없는 조합은 의미가 간단하다.
          // 이번 index의 원소를 뽑거나 안 뽑거나이다.
          // 이번 원소를 뽑고 전달한다.
          output.add(arr[idx]);
          combination(idx+1, output);
           
          // 뽑지 않은 경우는 위에서 넣었던 원소를 다시 빼서 전달한다.
          output.remove(output.size()-1);
          combination(idx+1, output);
           
     }
}