백준 12101 1, 2, 3 더하기 2 Kotlin (순열)

문제 출처 : https://www.acmicpc.net/problem/12101

12101번: 1, 2, 3 더하기 2

문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

• 1+1+1+1
• 1+1+2
• 1+2+1
• 2+1+1
• 2+2
• 1+3
• 3+1

이를 사전순으로 정렬하면 다음과 같이 된다.

1. 1+1+1+1
2. 1+1+2
3. 1+2+1
4. 1+3
5. 2+1+1
6. 2+2
7. 3+1

정수 n과 k가 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법 중에서 k번째로 오는 식을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 n과 k가 주어진다. n은 양수이며 11보다 작고, k는 231-1보다 작거나 같은 자연수이다.

출력

n을 1, 2, 3의 합으로 나타내는 방법 중에서 사전 순으로 k번째에 오는 것을 출력한다. k번째 오는 식이 없는 경우에는 -1을 출력한다.

알고리즘 분류

• 브루트포스 알고리즘
• 백트래킹

풀이

1,2,3을 이용한 순열로 n을 만드는 방법들을 나열하고, 이를 사전순으로 정렬하여 m번째 방법을 출력하면 된다.

백트래킹 알고리즘으로 순열만 만들 수 있으면 풀 수 있는 문제이고,

주의해야 할 점은 깊은 복사 정도? 

입력값이 크지 않기 때문에 그냥 String을 써도 되고, StringBuffer를 써도 되고 자유다.

코드

val br = System.`in`.bufferedReader()

//n을 1,2,3으로 나타내고 사전순정렬해서 m번째 값 출력
//없으면 -1
val result = arrayListOf(StringBuffer())
fun permutation(sum : Int, n : Int, strBfr : StringBuffer){

    val newBfr = StringBuffer(strBfr);

    if(sum>=n){
        if(sum==n){
            result.add(newBfr);
        }
        return;
    }

    for(i in 1 .. 3){
        permutation(sum+i,n,newBfr.append(i.toString()))
        newBfr.deleteCharAt(newBfr.length-1)
    }
}

fun main() = with(System.out.bufferedWriter()){

    val (n,m) = br.readLine().split(' ').map{it.toInt()}

    permutation(0,n, StringBuffer())
    result.sortBy{it.toString()}
    if(m !in result.indices){
        write("-1")
    }
    else{
        for(i in result[m].indices){
            if(i==result[m].length-1){
                write("${result[m][i]}")
            }
            else
            write("${result[m][i]}+")
        }
    }
    close()
}