본문 바로가기
PS 문제 풀이/Baekjoon

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

by 까망 하르방 2021. 5. 9.
반응형

출처: 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 시리즈)

순열과 조합 순열(Permutation) / 조합(Combination)에서 개수를 구하는 경우에는 아래 공식을 이용하면 되지만 순열 및 조합으로 경우의 수가 필요한 경우에는 재귀를 이용해야한다. ① P(4, 3) = 4 x 3 x 2

zoosso.tistory.com

 

활용 문제

- [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);
           
     }
}

 

반응형

'PS 문제 풀이 > Baekjoon' 카테고리의 다른 글

[BOJ] 백준 15663 N과 M(9)  (0) 2021.05.09
[BOJ] 백준 15649 N과 M (1)  (0) 2021.05.09
[BOJ] 백준 15654 N과 M(5)  (0) 2021.05.09
[BOJ] 백준 2440 별 찍기 - 3  (0) 2021.04.18
[BOJ] 백준 2441 별찍기 - 4  (0) 2021.04.18

댓글