250x250
08-17 21:55
관리 메뉴

막내의 막무가내 프로그래밍 & 일상

[알고리즘] 백준 2661 좋은수열 -백트래킹- 코틀린 본문

알고리즘/DFS, BFS, 시뮬, 백트래킹

[알고리즘] 백준 2661 좋은수열 -백트래킹- 코틀린

막무가내막내 2021. 6. 26. 22:06
300x250
SMALL

 

 

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

 

2661번: 좋은수열

첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다.

www.acmicpc.net

 

백준 2661 좋은수열이라는 백트래킹 유형 문제를 풀어봤습니다. ㅎㅎ

 

인접한 두 개의 부분 수열이 동일한게 없는게 좋은수열이며 이를 만족하는 가장 작은 수를 구하는 문제였습니다.

가장 중요한 부분은 check() 함수로 끝에서부터 1,2,3... 개로 양쪽으로 나눠 동일한 부분수열을 가졌는지 체크해줍니다.

 

 

풀이는 다음과 같습니다.

 

[Kotlin]

import java.util.*
import kotlin.system.exitProcess


lateinit var arr: IntArray
var n: Int = 0
fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    n = sc.nextInt()
    arr = IntArray(n)
    dfs(0, "")
}

fun dfs(depth: Int, num: String) {
    if (depth == n) {
        println(num)
        exitProcess(0) // 가장 작은수 발견 종료
    }
    for (i in 1..3) {
        if (check(num + i)) {
            dfs(depth+1, num + i)
        }
    }
}

// 좋은 수열인지 검사
fun check(num: String): Boolean {
    for (i in 1..num.length / 2) {
        val left = num.substring(num.length - i * 2, num.length - i)
        val right = num.substring(num.length - i, num.length)
        if (left == right) return false
    }
    return true
}

https://github.com/mtjin/algorithm_practice/commit/75f71f413759e0c219ca9c5300d6c0f0ec2ab50d

 

백준 2661 풀이 · mtjin/algorithm_practice@75f71f4

 

github.com

 

 

댓글과 공감은 큰 힘이 됩니다. 감사합니다. !!!

300x250
LIST
"이 포스팅은 쿠팡 파트너스 활동의 일환으로, 이에 따른 일정액의 수수료를 제공받습니다."
4 Comments
댓글쓰기 폼