개발해요

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

안녕하세요, 이륙사입니다.

풀이

이번 문제는 백트래킹을 활용한 완전 탐색(brute force) 문제였습니다.

우선, 좋은 수열이란 무엇이고 나쁜 수열과 어떻게 구분지을 수 있을까요?

좋은 수열이란, 가장 끝자리부터 1자리, 2자리, 계속해서 인접 숫자들을 확인했을 때 같은 숫자가 없는 것을 말합니다.

그리고 이 과정을 통해 한 자리씩 추가해가면서 전체 수열을 만든다는 아이디어와 각 자리수를 만들 때마다 좋은/나쁜 수열을 판별해야겠다는 생각을 자연스럽게 떠올릴 수 있습니다. 어떤 수가 좋은 수열이라면, 그것의 부분 수열들도 모두 좋은 수열이어야 합니다. 

이 아이디어가 중요한 이유는 n자리를 만들고나서 좋은 수열인지 판별을 하면 3^80가지를 확인하기 때문입니다. 하지만 뒤에 자리수를 추가할 때마다 좋은 수열인지 확인한다면, 미리 불필요한 탐색의 가지수를 줄일 수 있기 때문에 훨씬 빠른 시간 안에 탐색이 가능합니다. 그리고 이처럼 불필요한 탐색을 사전에 줄이는 것이 백트래킹으로 전부 확인하는 방법의 핵심입니다.

생각 과정

1. 좋은 수열과 나쁜 수열이란 무엇이고 그 둘을 어떻게 구별할지 생각한다.
2. 그 과정에서 뒤에 한자리씩 추가하면서 전체 가지수를 확인하고, 숫자를 추가할 때마다 수열을 판별한다는 생각을 떠올린다.

코드

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
}

*/

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

안녕하세요, 이륙사입니다.

풀이

이번 문제는 Union-Find 혹은 BFS, DFS를 사용해서 해결할 수 있는 문제였습니다. 그중에서 이번엔 BFS를 사용해서 포스팅해보려고 합니다.

먼저, 예시들을 통해 PU의 개수는 직사각형의 수와 관련이 있다는 걸 알 수 있습니다. 그리고 만약 한점 이상에서 만나는 직사각형들이 있다면 그 직사각형들은 연필을 떼지 않고 한번에 그릴 수 있습니다. 즉, 몇 번의 한붓 그리기로 모든 직사각형들을 그릴 수 있는지 묻고 있으며, 직사각형 집합의 개수를 구하는 문제로도 생각할 수 있습니다. (참고로 직사각형만 그릴 수 있기 때문에, 2, 3번 명령어는 고려하지 않아도 됩니다.)

따라서 집합의 수를 구하기 위해 Union-Find를 떠올릴 수 있으며, 겹치는 직사각형의 점들은 모두 연결되어 있기 때문에 인접한 곳을 모두 탐색하는 BFS, DFS로도 해결할 수 있게 되는 겁니다! 탐색 함수를 호출한 횟수가 집합의 개수가 됩니다. 

for (y in 0 until MAX_PLUS_ONE) {
        for (x in 0 until MAX_PLUS_ONE) {
            if (graph[y][x] == 1 && visited[y][x].not()) { // 직사각형이 있고, 아직 그룹지어지지 않았다면
                answer += 1
                bfs(x, y)
            }
        }
    }

좌표 변환

단순 그래프 탐색 문제가 되었으므로, 열심히 구현해서 정답을 제출합니다. 그리고 틀립니다. 왜냐면 아래와 같이 겹치지 않는데도 인접하는 상황이 발생하기 때문입니다.

이럴 때 좌표 값을 2배 늘려주면, 거리가 1이던 점들의 거리도 2가 돼서 문제를 해결할 수 있습니다! 또한, 좌표값은 양수이어야 하므로 먼저 +500 증가시킨 후에 좌표 값을 2배 늘려줍니다.

repeat(n) {
        val st = StringTokenizer(readLine())
        drawRect(2 * (st.nextToken().toInt() + 500), // 좌표를 오른쪽으로 이동 후 2배 증가
            2 * (st.nextToken().toInt() + 500),
            2 * (st.nextToken().toInt() + 500),
            2 * (st.nextToken().toInt() + 500)
        )
    }

디버깅을 통해서나 아니면 처음부터 이런 상황을 떠올릴 수 있으면 정말 좋겠지만, 문제 경험이 풍부하지 않고선 쉽지 않을 것 같습니다ㅋㅋ

예외 처리

정말 마지막으로, 처음에 (0, 0)에서 연필을 내린 상태로 시작한다는 점도 주의해주셔야 합니다. (0, 0)과 이어진 사각형들은 처음에 연필을 올리지 않고 그릴 수 있기 때문입니다. 

// 처음에 (1000,1000)에 연필을 내린 상태에서 시작
if (graph[1000][1000] == 1) print(answer - 1)
else print(answer)

생각 과정

1. 예시를 통해 사각형 집합의 개수를 구하는 문제라는 것을 확인한다.
2. 그래프 안에서 집합의 개수를 구하는 방법을 떠올린다 -> Union-Find, DFS, BFS

코드

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

const val MAX_PLUS_ONE = 2001

val graph = Array(MAX_PLUS_ONE){
    IntArray(MAX_PLUS_ONE)
}
val visited = Array(MAX_PLUS_ONE) {
    BooleanArray(MAX_PLUS_ONE)
}
val dX = arrayOf(-1, 1, 0, 0)
val dY = arrayOf(0, 0, -1, 1)

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val n = readLine().toInt()
    var puCount = 0

    repeat(n) {
        val st = StringTokenizer(readLine())
        // 좌표를 오른쪽으로 이동 후 2배 증가
        val x1 = 2 * (st.nextToken().toInt() + 500); val y1 = 2  * (st.nextToken().toInt() + 500)
        val x2 = 2 * (st.nextToken().toInt() + 500); val y2 = 2 * (st.nextToken().toInt() + 500)

        drawRectangle(x1, y1, x2, y2)
    }

    for (y in 0 until MAX_PLUS_ONE){
        for (x in 0 until MAX_PLUS_ONE) {
            // 직사각형이 있고, 아직 그룹지어지지 않았다면
            if (graph[y][x] == 1 && visited[y][x].not()) {
                bfs(x, y)
                puCount++
            }
        }
    }

    // 연필은 (1000,1000)에 내린 상태에서 시작한다
    if (graph[1000][1000] == 1) print(puCount - 1)
    else print(puCount)
}

// 직사각형 그리기
fun drawRectangle(x1: Int, y1: Int, x2: Int, y2: Int) {
    for (i in y1..y2) {
        graph[i][x1] = 1
        graph[i][x2] = 1
    }

    for (i in x1 + 1 until x2) { // 변끼리 겹치는 점 제외
        graph[y1][i] = 1
        graph[y2][i] = 1
    }
}

fun bfs(startX: Int, startY: Int) {
    val q: Queue<Pair<Int, Int>> = LinkedList()
    q.add(Pair(startX, startY))
    visited[startY][startX] = true

    while (q.isNotEmpty()) {
        val (x, y) = q.poll()

        for (i in 0 until 4) {
            val nextX = x + dX[i]
            val nextY = y + dY[i]

            if (nextX !in 0 until MAX_SIZE || nextY !in 0 until MAX_SIZE) continue

            if (graph[nextY][nextX] == 1 && visited[nextY][nextX].not()) {
                visited[nextY][nextX] = true
                q.add(Pair(nextX, nextY))
            }
        }
    }
}

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

안녕하세요, 이륙사입니다.

풀이

위 문제는 비용이 키 차이와 관련있다는 사실에서부터 시작하는 문제였습니다.

인접한 원생들의 키 차이를 값으로 갖는 새로운 수열을 구합니다. 그리고 그 수열의 합에서 값이 가장 큰 k-1개의 값을 빼면 그것이 정답이 됩니다. 왜냐하면 (큰 키 - 작은 키)의 값은 그 사이에 있는 원생들간 키 차이의 합과 같기 때문입니다. 그리고 아래 예시처럼 조를 k개로 나누면 k-1개의 경계가 생기며, 그 경계에 해당하는 차이 값들만 비용을 계산하는데 사용되지 않습니다. 따라서, 전체 차이의 합에서 가장 큰 k-1개를 빼주면 그것이 답이 됩니다.

예)

7, 3

1 3 5 6 10 16 19

또한, 전체 값의 합에서 가장 큰 값들을 빼주기 때문에 그리디 유형의 문제라고 할 수 있습니다. 

생각 과정

1. 학생 수가 최대 300,000이므로, 전부 확인해볼 순 없다.
2. 비용은 조에서 가장 키가 큰 학생과 가장 작은 학생의 차이다 --> 값의 차이에 주목한다.
3. 인접 원소들간 차이에 대해서도 생각해볼 수 있다.
4. 가장 키가 큰 학생과 작은 학생의 키 차이는 두 학생 사이에 있는 학생들간 키 차이의 합이란 것을 발견한다.
5. 조를 나누어본 결과, 비용의 합은 전체 키 차이의 합에서 가장 큰 k-1개의 값을 뺀 값이라는 것을 확인한다.

코드

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
import kotlin.math.sqrt

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val (n, k) = readLine().split(" ").map{ it.toInt() }
    val st = StringTokenizer(readLine())
    val gaps = IntArray(n) { st.nextToken().toInt() }
    
    // 인접 학생간 키차이를 값으로 갖는 수열
    for (i in 0 until n-1) {
        gaps[i] = gaps[i+1] - gaps[i]
    }

    // k개로 나누면 k-1개의 경계가 생긴다
    gaps.sort() // 전체에서 값이 큰 경계 k-1개를 빼기 위해 먼저 정렬한다  
    
    // 가장 큰 k-1개를 뺀 나머지를 모두 더한다
    val min = (0 until (n-1)-(k-1)).sumOf { i -> gaps[i] }
    print(min)
}

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

풀이

1. 투포인터 방법(left, right)을 사용한다.
2. 짝수, 홀수 카운팅(evenCount, oddCount)를 위한 변수와 최소 길이를 저장할 정답(answer) 변수를 선언한다. right 포인터는 0부터 시작한다.
3. right 포인터로 홀수를 k+1개 찾을 때까지 숫자를 차례대로 확인하면서 홀, 짝의 개수를 카운팅한다.
4. 홀수가 k+1개가 됐을 때,
   1. 지금의 짝수 개수가 k+1번째 홀수의 왼쪽에 있는 홀수 k개를 지웠을 때의 연속 짝수 길이가 된다. 따라서 이것을 지금까지 구한 정답과 비교한다
   2. left를 현재 구간의 첫번째 홀수 인덱스 + 1이 될 때까지 증가시킨다. 그 과정에서 짝,홀수의 개수를 감소시킨다.
5. 3, 4번 로직을 right가 전체 수의 길이보다 크거나 같아질 때까지 반복한다.
6. 홀수가 k개 이하일 경우를 대비하기 위해, 3,4,5번 반복문 종료 후 eventCount + oodCount == 전체 수의 길이인지 확인한다. true이면 eventCount가 정답이 된다. 

생각 과정과 후기

실버1이었는데 개인적으로 정말 정말 어려웠다.

우선 홀수를 어떻게 지워야 가장 긴 짝수를 만들 수 있을지 고민했다. 그리고 인접한 홀수들을 지울 때 가장 긴 짝수를 구할 수 있을 거라고 생각했다. 왜냐면, 만약 아래처럼 띄엄띄엄 지운 케이스가 정답이라고 가정해보면, 왼쪽에 있는 더 긴 범위가 정답일 것이다. 하지만 오른쪽 범위에서 지운 홀수 대신 가운데에 있는 홀수를 지우면 구간을 만들 수 있기 때문에 가정에 모순이 된다. 그래서 띄엄띄엄 지웠을 때는 정답을 구할 수 없다고 논리적으로도 확신할 수 있었다.

이제 구현만 하면 되는데, 그게 쉽지 않았다.

처음에는 홀수들의 인덱스를 리스트에 따로 저장해서 차례대로 k개를 지울 때마다 연속 짝수의 길이를 구하려고 했다. 하지만 지울 때마다 양 끝에 있는 홀수들의 바깥쪽에 짝수가 있는지, 있다면 몇개나 있는지를 알아내는 것이 쉽지 않았다. 그래도 나름대로 코드를 짜서 돌려봤는데 잘 안됐고, 결국 다른 분들 풀이를 참고했다.

풀이법을 어떻게 떠올릴 수 있었을까?

1. 인접한 홀수들을 왼쪽에서 오른쪽 순서대로 탐색한다 --> 구간을 옮긴다는 개념을 떠올릴 수 있다.

2. 홀수 범위를 알더라도 양 옆에 짝수가 어떻게, 몇 개나 있는지도 알아야 한다 -> 짝, 홀을 모두 고려해야 한다.

==> 순서대로 모든 수를 탐색하면서 + 짝 홀 두 가지를 다 신경써야 한다 + 구간을 옮긴다 -> 투포인터

이런 과정으로 떠올릴 수 있지 않았을까?

코드

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
import kotlin.math.max

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val st = StringTokenizer(readLine())
    val numberSize = st.nextToken().toInt()
    val removeSize = st.nextToken().toInt()
    val numbers = with(StringTokenizer(readLine())) {
        IntArray(numberSize) {
            this.nextToken().toInt()
        }
    }

    var answer = 0
    var left = 0
    var right = 0
    var evenCount = 0
    var oddCount = 0

    while (right < numberSize) {
        if (numbers[right++] % 2 == 0) evenCount++
        else oddCount++

        // k+1번째까지 찾아야 k번째 홀수 오른쪽에 있는 짝수들을 계산할 수 있다.
        if (oddCount > removeSize) {
            answer = max(answer, evenCount)

            // 가장 왼쪽에 있는 홀수를 찾을 때까지 증가시킨다
            while (numbers[left] % 2 == 0){
                left++
                evenCount--
            }
            left++ // 투포인터 범위를 가장 왼쪽에 있던 홀수 오른쪽부터 시작하도록 옮긴다
            oddCount--
        }
    }

    if (evenCount + oddCount == numberSize) {
        answer = evenCount
    }
    print(answer)
}