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

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

15651번: N과 M (3)

문제

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

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

해설

N과 M(1), (2)번 문제를 풀고 왔다면 더 수월하게 풀 수 있을 것이다.

이 문제부터 접한다면 아래 N과 M(1)번 포스팅을 확인해보는 것도 좋을 것이다.

https://jjunsu.tistory.com/98

[백준/BOJ] 15469번: N과 M (1)

백트래킹과 DFS를 사용하여 문제를 풀어보자.

 

문제의 조건으로 1~n까지의 수를 m개씩 조합한다. 또한 같은 수를 여러 번 뽑을 수 있다.

이제 재귀함수를 만든다.

1부터 시작하여 m만큼의 수의 조합을 뽑는다.

예제 2번을 보자면 1 1, 1 2, 1 3, 1 4와 같이 가장 마지막 노드(위치)까지 탐색을 한 후 더 이상 탐색할 노드가 없을 시

처음으로 돌아와 다시 탐색을 시작하게 된다.

소스 코드

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(idx: Int) {
        if(idx == m) {
            array.forEach { i -> sb.append("$i ") }
            sb.append("\n")
            return
        }
        for(i in 1 .. n) {
            array[idx] = i
            dfs(idx+1)
        }
    }

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