[백준] 15650번: N과 M (2)

문제 내용

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

15650번: N과 M (2)

 

풀이 시간

4분

풀이 과정

1. (python만) 라이브러리를 이용해서 간단하게 풀이(itertools.combinations 사용)

2. back_tracking을 이용해서 오름차순 조합 구현.

 

정답 코드

 

1. 파이썬

import sys
from itertools import combinations
sys_input=sys.stdin.readline

n,m=map(int,sys_input().rstrip().split())


# 1번 풀이:itertools 사용
for ans in combinations(range(1,n+1),m):
    for x in ans:
        print(x,end=" ")

    print()


# 2번 풀이: backtracking 사용
arr=[i for i in range(1,n+1)]
ans=[]

def back_tracking(prev):
    if len(ans)==m:
        for x in ans:
            print(x,end=" ")
        print()
        return

    if m-len(ans)>n-1-prev:
        return

    for i in range(prev+1,n):
        ans.append(arr[i])
        back_tracking(i)
        ans.pop()

back_tracking(-1)

 

 

2. 자바

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

public class p15650 {
    public static List<Integer> ans = new ArrayList<>();
    public static List<Integer> arr = new ArrayList<>();
    public static int n, m;

    public static void back_tracking(int prev) {
        if (ans.size() == m) {
            for (int x : ans) {
                System.out.print(x + " ");
            }
            System.out.println();
            return;
        }

        if (m - ans.size() > n - 1 - prev) {
            return;
        }

        for (int idx = prev + 1; idx < n; idx++) {
            ans.add(arr.get(idx));
            back_tracking(idx);
            ans.remove(ans.get(ans.size() - 1));
        }
    }

    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());

        for (int i = 1; i <= n; i++) {
            arr.add(i);
        }

        back_tracking(-1);
    }
}