[백준/BOJ] 15652번: N과 M(4)

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

15652번: N과 M (4)

문제

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

• 1부터 N까지 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.
• 고른 수열은 비내림차순이어야 한다.
  • 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.

해설

이전에 포스팅한 15651번: N과 M(3)을 풀었다면 쉽게 풀 수 있다.

만약 아직 N과 M(3)을 풀어보지 않았다면 아래의 포스팅을 보고 오면 좋을 것이다.

https://jjunsu.tistory.com/108

[백준/BOJ] 15651번: N과 M(3)

15651번과 달라진 것이라고는 수열이 비내림차순이라는 것이다.

비내림차순은 중복이 허용된다.

따라서 반복문의 i값을 시작점 변수로 재귀함수에 넣었다.

소스 코드

import java.lang.StringBuilder

fun main() = with(System.`in`.bufferedReader()) {
    val (n, m) = readLine().split(" ").map{ it.toInt() }
    val sb = StringBuilder()
    val array = IntArray(m)

    fun dfs(at:Int, idx: Int) {
        if(idx == m) {
            array.forEach { i -> sb.append("$i ") }
            sb.append("\n")
            return
        }
        for(i in at .. n) {
            array[idx] = i
            dfs(i, idx + 1)
        }
    }

    dfs(1,0)
    println(sb.toString())
}