[2023-05-07] 28015 영역 색칠 (Kotlin)

 

 

문제 링크: https://www.acmicpc.net/problem/28015

28015번: 영역 색칠

 

고작 실버 3 따리 문제지만, 삽질을 하도 많이 해서 올려봅니다.

 

 

 

첫 번째 시도(틀렸습니다.)

 

package thirtyseventh
import java.io.*
fun main(){
    val br = BufferedReader(InputStreamReader(System.`in`))
    val (n,m) = br.readLine().split(' ').map{it.toInt()}
    val arr = Array(n){Array(m){0} }
    
    // 횟수를 저장할 dp 배열
    val dp = Array(n){Array(m){0} }
    
    repeat(n){
        val list = br.readLine().split(' ').map{it.toInt()}
        for (index in list.indices){
            arr[it][index] = list[index]
        }
    }

	
    for (index in 0 until n){
    	// 각 반복 때마다, 0번 째의 dp 배열을 초기화 해줍니다.
        // 해당 영역의 값이 0이면 0, 1이나 2이면 한 번 칠한 것이므로 1로 저장합니다.
        if (arr[index][0] != 0)
            dp[index][0] = 1
            
        for (index1 in 1 until m){
        	
            // 현재의 영역 값
            val cur = arr[index][index1]
            // 이전의 영역 값
            val prev = arr[index][index1 - 1]
			
            // 현재의 영역값이 0이면, 이전 dp 배열의 값을 그대로 저장합니다.
            if (cur == 0){
                dp[index][index1] = dp[index][index1-1]
            }
            // 0 이 아닐 때,
            else{
            	// 현재 영역값이 이전 영역값과 다르면, 이전 dp 값의 +1을 저장
                // 같을 경우, 이전 dp 배열의 값을 그대로 저장합니다.
                if (cur != prev)
                    dp[index][index1] = dp[index][index1-1] + 1
                else
                    dp[index][index1] = dp[index][index1-1]
            }
        }
    }
    
    // 각 dp 배열의 층마다 마지막 값을 모두 더합니다.
    var count = 0
    for (index in 0 until n){
        count += dp[index][m-1]
    }
    println(count)

}

 

 

 

논리가 완벽하다 생각을 했습니다. 

 

문제를 잘못 이해하고 있나 싶어서 다시 꼼꼼히 읽어봤습니다.

 

 

 

 

 

저   "덧칠이 가능하다."라는 문장이 눈에 띄었습니다.

 

만약 한 줄에  1   1   1   1   1   2   1   1   1   2라는 입력값이 들어왔을 경우,

 

첫 번째 풀이에서는 횟수를  4로 계산을 했습니다.

 

 

 

하지만 덧칠이 가능할 경우,

 

전체를 1로 칠하는 횟수 = 1

 

2 만 칠하는 횟수 = 2 로 총횟수가 3이 나옵니다.

 

 

논리를 수정해서 다시 코드를 작성하였습니다.

 

 

두 번째 시도 (맞았습니다.)

 

package thirtyseventh
import java.io.*
fun main(){
    val br = BufferedReader(InputStreamReader(System.`in`))
    val (n,m) = br.readLine().split(' ').map{it.toInt()}
    val arr = Array(n){Array(m){0} }
    val dp = Array(n){Array(m){0} }
    repeat(n){
        val list = br.readLine().split(' ').map{it.toInt()}
        for (index in list.indices){
            arr[it][index] = list[index]
        }
    }

    for (index in 0 until n){
    
    	// 기준이 되는 변수를 만들었습니다.
        // 각 줄마다 첫 번째 영역값이 0일 경우는 -1, 
        // 1과 2일 경우는 각 영역값을 저장합니다.
        var first = -1
        if (arr[index][0] != 0){
            first = arr[index][0]
            dp[index][0] = 1
        }

        for (index1 in 1 until m){
            val cur = arr[index][index1]
            val prev = arr[index][index1 - 1]
            
            // 현재의 영역값이 0일 경우, first 변수에 -1을 저장합니다.
            if (cur == 0){
                dp[index][index1] = dp[index][index1-1]
                first = -1
            }
            
            // 현재의 영역값이 0이 아닐 때
            else{
            	// first 값이 -1일 경우, 이전 값이 0이라는 뜻이므로
                // first 변수에 현재 영역값 저장, 
                // dp 배열의 이전의 값에 1을 더한 값을 저장합니다.
                if (first == -1){
                    first = cur
                    dp[index][index1] = dp[index][index1-1] + 1
                }
                
                // first 값이 -1이 아닐 경우
                else{
                	// 현재의 값이 first 값과 같을 경우
                    // 이전 값과 같은 경우이므로 dp 배열의 이전의 값을 그대로 저장
                    if (cur == first)
                        dp[index][index1] = dp[index][index1-1]
                        
                    // 현재의 값이 first 값과 다를 경우
                    // ex) 1 1 1 1 2 2 1 2 
                    // 저 가운데 2 2 부분은 한 붓으로 칠할 수 있다.
                    else{
                    
                    	// 현재의 값과 이전의 값이 다를 경우
                        // dp 이전 배열의 값에 +1 한 값을 저장
                        if (cur != prev)
                            dp[index][index1] = dp[index][index1-1] + 1
                            
                        // 같을 경우 -> ex) 2 2
                        // dp 배열의 이전의 값을 그대로 저장
                        else
                            dp[index][index1] = dp[index][index1-1]
                    }

                }
            }
        }
    }
    // dp 배열의 층마다 마지막 값을 더하기
    var count = 0L
    for (index in 0 until n){
        count += dp[index][m-1]
    }
    println(count)

}

 

 

 

 

 

실버 3 문제중에 가장 어려웠던 것 같아요..