백준 15651) N과 M (3)

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

15651번: N과 M (3)

문제

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

 

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

입력

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

출력

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

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

 

---

 

시간 복잡도

 

 

N, M 모두 1-7 까지의 범위를 갖고 중복을 허용한다.

 

1) 1-N 중에서 1을 골랐을 시 : N

2) 1-N 중에서 1을 골랐을 시 : N

3) 1-N 중에서 2를 골랐을 시 : N

...

 

모든 경우의 수를 곱하게 되면 시간복잡도는 O(N^N) 이 된다.

여기서 for문으로 1-N까지 반복했을 때의 시간복잡도는 O(N)이다.

결국 O(N) * O(N^N) = O(N^N+1) 이 총 시간복잡도가 된다.

문제의 제한 시간은 1초이고 데이터의 크기가 1억정도일 때 1초라고 한다면

7^(7+1) = 5764801 로 주어진 시간 내에 충분히 해결할 수 있다.

 

 

 

접근 방법

 

 

• arr : IntArray - 가능한 경우를 저장하는 배열
• go : Function - 재귀 호출할 함수

 

1. 재귀 함수를 구현하기 위해 매개 변수를 정한다.

 

조건을 만족하면 증가하는 변수 : idx

idx==m 일 때 return 해야 함 : m

1부터 N까지의 수를 구해야 함 : n

 

go(idx : Int, n : Int, m : Int)

 

 

 

2. 다음 경우를 호출하는 방법을 고려한다.

 

중복을 허용하므로 arr 배열에 i 값을 저장한다.

 

go(idx+1, n, m)

 

 

 

3. 조건을 만족하는 경우를 고려한다.

 

idx와 m이 동일할 때 m개의 순열을 출력할 수 있으므로

if(idx==m) 조건에 도달하게 될 경우, arr 배열에 저장했던 값들을 출력하면 된다.

 

 

 

4. 불가능한 경우를 고려한다.

 

이 문제에서는 불가능한 경우는 존재하지 않는다.

 

 

 

코드

 

lateinit var arr: IntArray
lateinit var check: BooleanArray
val sb = StringBuilder()
fun main() = with(System.`in`.bufferedReader()) {
    val (n, m) = readLine().split(" ").map { it.toInt() }
    arr = IntArray(m)
    check = BooleanArray(n + 1)
    go(0,n,m)
    print(sb)
}

private fun go(idx: Int, n: Int, m: Int) {
    if (idx == m) {
        arr.forEach { sb.append(it).append(' ') }
        sb.append("\n")
        return
    }
    for (i in 1..n) {
        arr[idx] = i
        go(idx + 1, n, m)
    }
}