728x90
SMALL
백트래킹을 통한 재귀구현
이미 완성된 수열의 경우 좋은수열로 판단하여 추가로 들어오는 값에대한 앞과 뒤를 확인하면 된다.
fun main() = with(Scanner(System.`in`)) {
val count = nextInt()
var result = ""
fun backTracking(n: Int, str: String, index: Int) {
if(!canMake(str)){
return
}
if (index == n) {
if(result.isEmpty()){
result = str
return
}
for(i in str.indices){
if(result[i] < str[i]){
return
}
}
result = str
return
}
for (i in 1..3) {
backTracking(n, str + i.toString(), index + 1)
}
}
backTracking(count, "", 0)
println(result)
}
fun canMake(str: String): Boolean {
for (i in 1 .. str.length / 2) {
val start = str.substring(str.length - i * 2, str.length - i)
val end = str.substring(str.length - i, str.length)
if(start == end) return false
}
return true
}
728x90
LIST
'IT > 알고리즘' 카테고리의 다른 글
[백준] 차이를 최대로 (0) | 2024.11.14 |
---|---|
[백준] 퇴사 (1) | 2024.11.12 |
[백준] 단어수학 (2) | 2024.11.11 |
[프로그래머스] 3xn 타일링 (0) | 2024.11.11 |
[백준] 부분수열의 합 (0) | 2024.11.06 |