https://www.acmicpc.net/problem/2661
2661번: 좋은수열
첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다.
www.acmicpc.net
안녕하세요, 이륙사입니다.
풀이
이번 문제는 백트래킹을 활용한 완전 탐색(brute force) 문제였습니다.
우선, 좋은 수열이란 무엇이고 나쁜 수열과 어떻게 구분지을 수 있을까요?
좋은 수열이란, 가장 끝자리부터 1자리, 2자리, 계속해서 인접 숫자들을 확인했을 때 같은 숫자가 없는 것을 말합니다.
그리고 이 과정을 통해 한 자리씩 추가해가면서 전체 수열을 만든다는 아이디어와 각 자리수를 만들 때마다 좋은/나쁜 수열을 판별해야겠다는 생각을 자연스럽게 떠올릴 수 있습니다. 어떤 수가 좋은 수열이라면, 그것의 부분 수열들도 모두 좋은 수열이어야 합니다.
이 아이디어가 중요한 이유는 n자리를 만들고나서 좋은 수열인지 판별을 하면 3^80가지를 확인하기 때문입니다. 하지만 뒤에 자리수를 추가할 때마다 좋은 수열인지 확인한다면, 미리 불필요한 탐색의 가지수를 줄일 수 있기 때문에 훨씬 빠른 시간 안에 탐색이 가능합니다. 그리고 이처럼 불필요한 탐색을 사전에 줄이는 것이 백트래킹으로 전부 확인하는 방법의 핵심입니다.
생각 과정
- 좋은 수열과 나쁜 수열이란 무엇이고 그 둘을 어떻게 구별할지 생각한다.
- 그 과정에서 뒤에 한자리씩 추가하면서 전체 가지수를 확인하고, 숫자를 추가할 때마다 수열을 판별한다는 생각을 떠올린다.
코드
import java.io.BufferedReader
import java.io.InputStreamReader
import kotlin.system.exitProcess
var n = 0
fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
n = readLine().toInt()
findMinGood("")
}
fun findMinGood(number: String) {
if (number.length == n){
print(number)
exitProcess(0)
}
for (i in 1..3){
if (isGood(number + i)){
findMinGood(number + i)
}
}
}
fun isGood(number: String): Boolean {
val length = number.length
for (i in 1..length / 2) {
val left = number.substring(length - 2 * i , length - i)
val right = number.substring(length - i ,length)
if (left == right) return false
}
return true
}
/* 아래와 같이 비교할 수도 있습니다
fun isGood(number: String): Boolean {
val length = number.length
for (i in 1..length / 2) { // 비교 길이
var isGood = false
for (j in 0 until i) { // 자리수
// 다른 숫자가 있다면
if (number[(length - 1) - j] != number[(length - 1) - j - i]) {
isGood = true
}
}
if (isGood.not()) return false
}
return true
}
*/
'Problem Solving > 백준' 카테고리의 다른 글
| 백준 2632번: 피자 판매 (Kotlin) (0) | 2022.01.21 |
|---|---|
| 백준 1261번: 알고스팟 (Kotlin) (0) | 2022.01.20 |
| 백준 3108번: 로고 (Kotlin) (0) | 2022.01.18 |
| 백준 1525번: 퍼즐 (Kotlin) (0) | 2022.01.17 |
| 백준 2186번: 문자판 (Kotlin) (0) | 2022.01.16 |
