[백준 6603번] [Kotlin] 로또

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

6603번: 로또

 

난이도 : 실버 2
태그 : 수학, 조합론, 백트래킹, 재귀

 

 

설명

주어진 숫자 중 6개를 만드는 모든 조합을 찾는 문제입니다.

숫자 자체가 오름차순으로 주어지니, 입력 배열을 정렬할 필요는 없습니다.

 

저는 백트래킹(재귀)으로 주워진 숫자들의 모든 경우의 수를 체크하였습니다.

 

 

소스코드

import java.util.*

var n = 0
lateinit var arr: Array<Int>
lateinit var visited: Array<Boolean>
val sb = StringBuilder()

fun main() = with(System.`in`.bufferedReader()) {

    while (true) {

        val st = StringTokenizer(readLine())
        n = st.nextToken().toInt()

        if (n == 0) break

        arr = Array(n) { st.nextToken().toInt() }
        visited = Array(n) { false }

        backTracking(0, 0)
        sb.append("\n")
    }

    print(sb)
}


fun backTracking(depth: Int, lastIdx: Int) {

    if (depth == 6) {
        for (i in 0 until n) {
            if (visited[i]) {
                sb.append(arr[i]).append(" ")
            }
        }
        sb.append("\n")
    }

    for (i in lastIdx until n) {
        visited[i] = true
        backTracking(depth + 1, i + 1)
        visited[i] = false
    }
}

 

 

코드분석

1. 무한루프를 돌며 입력값이 0일때까지 반복

2. 방문여부를 체크할 visited 배열과 arr 배열 세팅

3. 백트래킹 진행

3 - 1. 재귀적으로 백트래킹을 진행하기 전에 방문 여부를 true로 바꿈

3 - 2. 백트래킹 탐색 진행 - 문자열 길이 (depth)를 +1, 마지막으로 탐색한 위치 +1하여 매개변수로 전달

3 - 3. 백트래킹을 완료하면 false로 변환

3 - 4. 백트래킹 탐색 중, 길이가 6(depth == 6)일 경우, visited가 true인 (방문을 한) 원소들을 모아 StringBuilder에 추가

4. StringBuilder 출력

 

 

후기

로또에 당첨되면 좋겠네요.