[BaekJoon] 15651번 N과 M (3) (Kotlin) 문제 풀이 [Silver 3]

문제

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

15651번: N과 M (3)

 

어떻게 풀 것인가?

문제를 처음 읽었을 때는 어떠한 문제를 파악하는지 꽤나 오랜 시간이 걸렸다.

 

하지만 주어진 문제의 출력 부분을 보고는 백트래킹을 이용한 중복 조합 문제를 생각했다.

 

조합과 순열은 수학적인 부분이지만 조합을 실제 코드로 구현한 부분에서 visited 부분을 제거한다면, 중복조합이 됨을 알 수 있다.

 

아래에 링크에 남겨두었지만, 저 코드를 그대로 사용한다면, 시간 초과가 발생할 것이다.

 

자주 사용하는 코드는 전역변수를 선언함과 동시에 불필요한 코드를 제거한다면 시간초과를 해결할 수 있을 것이다.

 

풀면서 놓쳤던점

X

 

이 문제를 통해 얻어갈 것

중복 조합 문제 해결 능력

 

내 코드 

import java.util.*;
import java.io.*;

// 백준알고리즘 15651번 N과 M (3)
private var N = 0;
private var M = 0;
private lateinit var arr: Array<Int>;
private val sb = StringBuilder();

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val st = StringTokenizer(br.readLine());
    N = Integer.parseInt(st.nextToken())
    M = Integer.parseInt(st.nextToken())

    arr = Array(M) { 0 }

    backTracking(0)
    println(sb)
} 

private fun backTracking(depth: Int) {

    if (M == depth) {
        arr.forEach {
            sb.append(it).append(' ')
        }
        sb.append('\n');
        return;
    }

    for (i in 1..N) {
        arr[depth] = i;
        backTracking(depth + 1);
    }

}

 

참고

https://velog.io/@cgw0519/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%88%9C%EC%97%B4-%EC%A4%91%EB%B3%B5%EC%88%9C%EC%97%B4-%EC%A1%B0%ED%95%A9-%EC%A4%91%EB%B3%B5%EC%A1%B0%ED%95%A9-%EC%B4%9D%EC%A0%95%EB%A6%AC

[알고리즘] 순열, 중복순열, 조합, 중복조합 총정리 !