백준 15656번 N과 M (7) (Java, Kotlin)

: ) YOUNG·2022년 6월 14일
1

알고리즘

목록 보기
149/417
post-thumbnail

백준 15656번
https://www.acmicpc.net/problem/15656

문제



N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다.

  • N개의 자연수 중에서 M개를 고른 수열
  • 같은 수를 여러 번 골라도 된다.

생각하기


동작



코드



Java

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

public class Main {
	static StringBuilder sb = new StringBuilder();
	static int N; static int M;
	static int arr[];
	static int ans[];	
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		arr = new int[N];
		ans = new int[M];
		
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(arr);
		
		DFS(0);
		bw.write(sb.toString());
		bw.flush();
		bw.close();
	} // End of main

	static void DFS(int depth) {
		
		if(depth == M) {			
			for(int i=0; i<M; i++) {
				sb.append(ans[i]).append(' ');
			}
			
			sb.append('\n');
			return;
		}
		
		for(int i=0; i<N; i++) {
			ans[depth] = arr[i];
			DFS(depth + 1);
		}
	} // End of DFS
} // End of Main class

Kotlin

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

private val sb = StringBuilder()
private lateinit var arr : IntArray
private lateinit var ans : IntArray
private var N = 0; private var M = 0

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.`out`))
    var st = StringTokenizer(br.readLine())

    N = st.nextToken().toInt()
    M = st.nextToken().toInt()
    arr = IntArray(N)
    ans = IntArray(M)

    st = StringTokenizer(br.readLine())
    for(i in 0 until N) {
        arr[i] = st.nextToken().toInt()
    }
    Arrays.sort(arr)
    DFS(0)
    bw.write(sb.toString())
    bw.flush()
    bw.close()
} // End of main

private fun DFS(depth : Int) {
    if(depth == M) {
        for(i in 0 until M) {
            sb.append(ans[i]).append(' ')
        }
        sb.append('\n')
        return;
    }

    for(i in 0 until N) {
        ans[depth] = arr[i]
        DFS(depth+1)
    }
} // End of DFS

0개의 댓글