백준 28015번
https://www.acmicpc.net/problem/28015

문제

---

생각하기

---

• 간단한 구현 그리디 문제이다.

  • 어렵지 않았는데 처음에 문제이해를 잘못해서 완전 다르게 풀었었따..

• 덧칠이 가능하고, 가로 방향으로 칠할 수 있다가 이 문제의 핵심이다.

  • 덧칠이 가능하기 때문에 0이 나오지 않는 이상 일직선으로 1로 모두 칠해놓고 2를 덧칠하거나, 2로 모두 칠해놓고 1을 덧칠하는 방법으로 최소한의 붓칠을 하는 횟수를 구하면 된다.
  • 결국에 가로 배열에서 0이 나오기까지의 숫자 배열을 만들어서 1과 2의 영역 개수를 구하면 되는 문제이다.

동작

코드

---

Kotlin

import java.io.*
import java.util.*

// input
private lateinit var br: BufferedReader

// variables
private var N = 0
private var M = 0
private var ans = 0

// 덧칠하면서 만난 다른 색깔
private var map = Array(101) { IntArray(101) }

fun main() {
    br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.out))
    val sb = StringBuilder()

    input()

    val list: MutableList<Int> = ArrayList()
    for (i in 0 until N) {
        for (j in 0 until M) {
            if (map[i][j] != 0) {
                list.add(map[i][j])
            } else if (map[i][j] == 0 && list.isNotEmpty()) {
                // 리스트에서 1과 2가 모두 동시에 포함되어 있는지를 확인
                if (list.contains(2) && list.contains(1)) {
                    // 1과 2가 동시에 있다면, 어떤 걸로 칠하고 덧칠했을 때, 가장 적은 횟수로 가능한지 확인해야 됨
                    // 적은 횟수로 덧칠할 수 있는 색깔을 구하고, 처음 칠하는 색상을 위해 붓질 한번 더하기
                    ans += check(list) + 1
                } else {
                    // 1과 2가 동시에 있지 않다면, 굳이 최솟값을 구할 필요가 없다.
                    ans += 1
                }

                list.clear()
            }
        }

        // 0을 만나지 못하고 끝났을 경우 고려
        if (list.contains(2) && list.contains(1)) {
            ans += check(list) + 1
        } else if (list.isNotEmpty()) {
            // 1과 2가 동시에 있지 않다면, 굳이 최솟값을 구할 필요가 없다.
            ans += 1
        }

        list.clear()
    }

    sb.append(ans)
    bw.write(sb.toString())
    bw.close()
} // End of main

private fun check(list: MutableList<Int>): Int {
    var oneColor = 0
    var twoColor = 0

    var preColor = list[0]
    if (preColor == 1) {
        oneColor = 1
    } else {
        twoColor = 1
    }
    var nowColor = -1
    val size = list.size
    for (i in 1 until size) {
        nowColor = list[i]
        if (preColor != nowColor) {
            if (nowColor == 1) {
                oneColor++
            } else {
                twoColor++
            }
        } else continue
        preColor = nowColor
    }

    return Math.min(oneColor, twoColor)
} // End of check

private fun input() {
    var st = StringTokenizer(br.readLine())
    N = st.nextToken().toInt()
    M = st.nextToken().toInt()

    for (i in 0 until N) {
        st = StringTokenizer(br.readLine())
        for (j in 0 until M) {
            map[i][j] = st.nextToken().toInt()
        }
    }
} // End of input