백준 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를 만족하면, 비내림차순이라고 한다.

입력

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

출력

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

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

 

 

---

 

시간 복잡도

 

 

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 로 주어진 시간 내에 충분히 해결할 수 있다.

 

 

 

 

접근 방법

 

 

이전의 N과 M 문제와 달리 비내림차순 이라는 개념이 등장했다.

 

비내림차순이란,

같은 수는 허용하되, 이하의 수는 허용하지 않는 것이다.

2 다음으로 2는 올 수 있지만, 1은 올 수 없다는 의미다.

 

 

이를 소스 코드로 어떻게 구현했는지 직접 코드를 보며 알아보도록 하겠다.

 

 

 

 

코드

 

lateinit var arr : IntArray
val res = StringBuilder()

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

    arr = IntArray(m)
    go(0,  1,n, m)
    println(res)
}

//idx : 답을 저장하는 배열의 index
//start : 비내림차순을 적용시키기 위한 첫 번째 단계.
///////// start 가 1이였다면 다음 호출에는 2부터 시작한다는 의미. 그래서 이전의 값 1이 호출될 수 없게 만듬
//n, m : 문제에 주어진 크기

private fun go(idx : Int, start : Int,n : Int, m :Int) {
	// 조건에 만족한 경우를 의미함
    // m 개를 다 채웠으므로 여기서 return.
    if(idx==m) {
    	// StringBuilder를 사용한 이유는 출력에 의한 속도를 보장하기 위함
        arr.forEach { res.append(it).append(' ') }
        res.append("\n")
        return
    }
    
    // start(=1) 부터 n 까지 for문을 돌림 
    for(i in start..n) {
    	// 주어진 i를 arr 배열에 저장
        arr[idx] = i
        // *중요*
        // start 인자로 i를 넘겨줌으로써 비내림차순을 비로소 만족시킬 수 있음.
        // 현재 호출에서 i=1 을 넘겼다면 다음 호출에서 i=1로 받으므로 1 -> 1, 1 와 같이 저장 가능.
        // 만약 i+1 이였다면, 1 -> 1, 2 로 저장됐을 것임.
        go(idx+1, i, n,m)
    }
}