개발해요

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)
}

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

풀이

골드5였는데 정말 정말 어려웠다.

지금껏 풀어봤던 문제들이랑 사고방식이 전혀 다르다는 느낌이 들었다. 구현이랑 완전 탐색 문제 경험이 부족한걸까.

처음에 그리디적으로 접근했는데 분기문이 감당이 안됐다. 브루트 포스 유형이란걸 알고나서도 어떻게 풀지 쉽게 떠오르지 않았다. 다른 분들 풀이를 참고했는데, 풀면서 멘탈이 나갔는지 처음엔 설명을 봐도 이해가 안됐다..ㅋㅋㅋ

알고나니까 컨셉은 간단했다!

버튼을 눌러서 한번에 이동할 수 있는 채널을 모두 구하는 것이다.

그러면, 모든 (이동 가능한 채널 i의 자리수) + (i에서 목표 채널 N(target)까지 거리) 중 최소 값과 100에서 N까지 +, -로 가는 거리 중 최소 값이 답이 된다.

순서

1. 고장난 버튼의 개수를 확인한다. 만약 버튼이 전부 고장났다면, +, -로 이동하는 횟수가 정답이다
2. 1개라도 고장나지 않았다면, 0 <= i <= 900,000에 대해, +, - 없이 i로 한번에 이동할 수 있는 수들을 확인한다.
3. 이동 가능한 수들의 i로 직접 버튼 클릭 + 절대값(N - i) 중 최소값을 구한다.
4. 위에서 구한 최소값과 100에서 N으로 곧장 가는 절대값(N - 100) 중 작은 값이 답이 된다. (N = 101 같은 케이스 고려)

900,000까지 탐색하는 이유는 다음과 같다.

문제가 원하는 답은 아래 3가지 경우 중 최소값이다

1. 100에서 N까지 바로 가는 경우
2. 100에서 i <= N인 i를 거쳐 가는 경우 (왼쪽에서 오른쪽)
3. 100에서 i > N인 i를 거쳐 가는 경우(오른쪽에서 왼쪽) 

그리고 2, 3번의 경우

• 왼쪽에서 오른쪽으로 가는 최대 횟수는 N = 500,000이고 고장나지 않은 버튼이 0인 경우의 100 -> 500,000인 499,900번,
• 오른쪽에서 왼쪽으로 가는 최대 횟수는 고장나지 않은 버튼이 0과 9인 경우의 100 -> 900,000 -> 500,000인 400,006번이다. 그 이상의 수를 확인해봤자 499,900번을 넘기 때문에 확인하지 않아도 된다.

좀 더 간단하게는 왼쪽 -> 오른쪽 최대 값이 약 50만이기 때문에 최대 숫자를 50만 + 50만 = 100만으로 설정해서,

0 <= i <= 1,000,000을 탐색할 수 있다!

코드1

import java.io.*
import java.util.StringTokenizer
import kotlin.math.*

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val target = readLine().toInt()
    val brokenCount = readLine().toInt()
    val broken = BooleanArray(10)

    // 버튼이 망가졌으면 true, 아니면 false
    if (brokenCount > 0){
        val st = StringTokenizer(readLine())
        repeat(brokenCount) {
            broken[st.nextToken().toInt()] = true
        }
    }

    // 전부 고장났으면 +, -로만 이동하는 게 정답
    if (brokenCount == 10 || target == 100) {
        print(abs(target - 100))
        return
    }

    // target = 101과 같은 경우 고려
    var minClicked = abs(target - 100)
    
    for (i in 0 until 900_000) {
        val number = i.toString()

        // i로 번호를 직접 입력해서 갈 수 있는지 확인한다.
        if (isReachable(number, broken)){
            val numberToTarget = abs(i - target) // i에서 target으로 +나-로 이동하는 횟수
            minClicked = min(minClicked, number.length + numberToTarget)
        }
    }

    print(minClicked)
}

// 각 자리수 중 하나라도 망가진 번호가 있으면 직접 거쳐갈 수 없다.
fun isReachable(target: String, broken: BooleanArray): Boolean {
    target.forEach{ ch ->
        val number = ch - '0'
        if (broken[number]) return false
    }

    return true
}

코드2 (각 자리수 확인할 때 문자열이 아닌 정수로 처리하는 버전)

import java.io.*
import java.util.StringTokenizer
import kotlin.math.*

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val target = readLine().toInt()
    val brokenCount = readLine().toInt()
    val broken = BooleanArray(10)

    if (brokenCount > 0){
        val st = StringTokenizer(readLine())
        repeat(brokenCount) {
            broken[st.nextToken().toInt()] = true
        }
    }

    if (brokenCount == 10 || target == 100) {
        print(abs(target - 100))
        return
    }

    var minClicked = abs(target - 100)
    for (i in 0 until 900_000) {
        val clickCount = getClickCount(i, broken)
        if (clickCount > 0){
            val iToTarget = abs(i - target)
            minClicked = min(minClicked, clickCount + iToTarget)
        }
    }

    print(minClicked)
}

fun getClickCount(target: Int, broken: BooleanArray): Int {
    var count = 0
    var targetNumber = target

    while(true) {
        val button = targetNumber % 10
        if (broken[button]) {
            return 0
        }

        count++
        targetNumber /= 10
        if (targetNumber == 0) break
    }

    return count
}

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

풀이

같은 유형의 작은 문제들로 계속 쪼개어지는 것으로 보아, 분할 정복 문제라는 것을 알 수 있었다. 그치만 시간 제한이 0.5초라서 주의해야 할 부분이 있었다.

행렬 표현

먼저 탐색에 앞서 행렬은 시작점과 각 변의 길이를 통해 나타낼 수 있다.

1. 시간 제한을 고려하지 않는 방법

1. (0, 0)과 전체 크기의 행렬을 대상으로 탐색을 시작한다.
2. 지금 탐색중인 행렬의 길이를 확인한다.
   1. 2보다 길거나 같으면, 길이를 2로 나눠서 Z모양에 따라 다시 재귀적으로 탐색한다.
   2. 길이가 1이고,
      1. 목표 지점이라면, 몇 번째로 방문했는지 저장하고 탐색을 종료한다.
      2. 목표 지점이 아니라면,해당 점의 위치를 확인하고 방문 순서(count)를 +1 증가시키고 재귀 탐색을 종료한다.
3. 목표점의 방문 순서를 출력한다.

이렇게 하면 항상 정답을 찾을 수 있다. 하지만 코드를 제출해보면 시간 초과가 발생한다.

📌시간 복잡도)

- (2^n * 2^n) 행렬의 길이가 1(한 점)이 될 때까지 2로 나누는 횟수 = log(2^n) = n

- 모든 점의 개수 = 2^n * 2^n

연산 횟수: (2^n * 2^n) * n = 2^15 * 2^ 15 * 15 = 약 160억

시간 복잡도: O(n*4^n)

따라서, 연산 횟수를 줄여야 한다. 그리고 아래의 그림과 같이 찾는 점이 존재하는 구간만 재귀적으로 탐색하면 시간 복잡도를 확 줄일 수 있다. 나머지 부분은 방문 순서만 업데이트 해준다.

2. 시간 복잡도를 개선한 방법

1. (2^n * 2^n) 행렬을 Z모양의 순서대로 탐색한다.
2. 지금 탐색중인 범위가 내가 찾으려고 하는 최종 범위(점)인지 확인한다.
   1. 찾던 점이라면, 몇 번째로 방문했는지 저장한다.
   2. 아니라면, Z방향 순서대로
      1. 목표지점을 포함하지 않는 곳은 방문 순서(visitCount)만 길이 * 길이만큼 증가시키고 탐색을 종료한다
      2. 목표지점을 포함하는 곳은 길이를 절반으로 나눠서 탐색을 계속한다.
3. 목표점의 방문 순서를 출력한다.

📌줄어든 시간 복잡도)

- 필요한 점을 찾기 위해 구간을 나누는 횟수 = log(2^n) = n,

- 나눌 때마다 방문 순서 업데이트 하는 연산 횟수 3번

연산 횟수: 3 * n = 3 * 15 = 45

시간 복잡도: O(n)

코드

import java.io.BufferedReader
import java.io.InputStreamReader

var answer = 0
var numbering = 0

// dudwls901님 풀이 참고 버전

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val input = readLine().split(" ").map{ it.toInt() }
    val (n, r, c) = input

    visitGraph(1 shl(n), 0, 0, r, c)
    print(answer)
}

fun visitGraph(size: Int, row: Int, col: Int, targetRow: Int, targetCol: Int) {

    // 탐색중인 Z구간에 목표지점이 없으면
    // 탐색하지 않고 방문 순서만 update하고 탐색을 종료한다
    if (targetRow !in row until row + size || targetCol !in col until col + size) {
        numbering += size * size
        return
    }

    // 목표지점을 찾았으면 방문 순서를 저장하고 리턴한다
    if (row == targetRow && col == targetCol) {
        answer = numbering
        return
    }

    val halfSize = size / 2

    visitGraph(halfSize, row, col, targetRow, targetCol) // 왼쪽 위
    visitGraph(halfSize, row, col + halfSize, targetRow, targetCol) // 오른쪽 위
    visitGraph(halfSize, row + halfSize, col, targetRow, targetCol) // 왼쪽 아래
    visitGraph(halfSize, row + halfSize, col + halfSize, targetRow, targetCol) // 오른쪽 아래
}