[백준] 15651번 N과 M (3) kotlin

쓰리원·2022년 5월 14일
1

코딩테스트

목록 보기
28/28
post-thumbnail

1. 백준 15651번 문제

1.문제

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

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

2.입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 7)

3.출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

2. 문제 해석

1) 1 ~ N 까지의 수 중 M 개를 선택하여 조합하기. (길이가 M이다)

2) 중복해서 조합 가능.

3) 1 부터 N까지 M의 길이 및 크기로 중복을 허용해서 조합할 수 있는 수를 오름차순으로 나열하는 문제입니다.

3. 문제 풀이

import java.util.*

internal var num : IntArray? = null
internal var N = 0
internal var M = 0
internal var sb = StringBuilder()

fun main() {
    val sc = Scanner(System.`in`)
    N = sc.nextInt()
    M = sc.nextInt()
    num = IntArray(M + 1)
    dfs(1)
    println(sb)
}

internal fun dfs(depth: Int) {
    if (depth > M) {
        for (i in 1..M) {
            sb.append(num!![i]).append(" ")
        }
        sb.append("\n")
        return
    }
    for (i in 1..N) {
        num!![depth] = i //!! 이므로 NULL값이 들어오면 안된다.
        dfs(depth + 1)
    }
}
profile
가장 아름다운 정답은 서로의 협업안에 있다.

0개의 댓글