[2023-05-04] 18111 마인크래프트 (Kotlin) + 9문제

 

 

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

18111번: 마인크래프트

 

 

유형을 몰라 많이 헤매었습니다.

 

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

// 한 줄의 리스트로 입력받은 높이를 모두 저장
// 높이를 저장할 dp 배열 생성
// 1 부터 index를 돌며
// 이전 index의 dp 배열의 높이와 다를 경우,
// 이전 것들의 높이를 맞추는 시간과, 현재 것의 높이를 내리는 시간을 비교하여 최소값을 기록
// 현재의 dp 배열에 고르게 맞춘 높이를 저장
// 블럭이 부족할 경우 무조건 현재의 것을 내리기


package thirtyfourth
import java.io.*
import java.util.*
fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val (n,m,b) = br.readLine().split(' ').map{it.toInt()}
    val arr = Array(n*m){0}
    val dp = Array(n*m){0}
    var start = 0
    repeat(n){
        val token = StringTokenizer(br.readLine())
        for (index in start until m+start){
            arr[index] = token.nextToken().toInt()
        }
        start += m
    }
    var have = b
    var time = 0
    dp[0] = arr[0]
    for (index in 1 until dp.size){
        val a = arr[index]
        val c = dp[index - 1]
        if (a > c){
            val diff = a - c
            val put = diff*index
            val remove = diff*2
            if (have - put < 0){
                time += remove
                have += diff
                dp[index] = dp[index - 1]
            }
            else{
                if (put <= remove){
                    time += put
                    have -= put
                    dp[index] = arr[index]
                }
                else{
                    time += remove
                    have += diff
                    dp[index] = dp[index - 1]
                }
            }
        }
        else if (a < c){
            val diff = c - a
            val put = diff
            val remove = diff*index*2
            if (have - put < 0){
                time += remove
                have += diff
                dp[index] = arr[index]
            }
            else{
                if (put <= remove){
                    time += put
                    have -= put
                    dp[index] = dp[index-1]
                }
                else{
                    time += remove
                    have += diff
                    dp[index] = arr[index]
                }
            }
        }
        else
            dp[index] = dp[index-1]
    }
    print("$time ")
    print(dp[n*m-1])
}

 

논리부터가 말이 안 됐습니다.

 

너무 마구잡이로 푸는 것 같아 회의감이 들었습니다.

 

감이 오지 않아, 문제 유형을 확인하였습니다.

 

 

 

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

 

// 문제의 유형은 브루트포스
// 블럭을 지우는 것보다는 쌓는게 더 시간이 덜 드므로
// 높이의 최소부터 최대까지 반복문을 통해 최소의 시간 소요값을 구하기

package thirtyfourth
import java.io.*
import java.util.*
fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val (n,m,b) = br.readLine().split(' ').map{it.toInt()}
    
    // 한 줄 배열 생성
    val arr = Array(n*m){0}
    var start = 0
    // 한 줄 배열에 차례대로 높이 저장
    repeat(n){
        val token = StringTokenizer(br.readLine())
        for (index in start until m+start){
            arr[index] = token.nextToken().toInt()
        }
        start += m
    }
    
    // 최대 최소 저장
    val max = arr.max()
    val min = arr.min()
    
    // 두 값이 같을 경우는 걸리는 시간이 0이므로 예외처리
    if (min == max)
        println("0 $min")
        
        
    else{
    	// 시간 소요값과 높이를 저장할 변수
        var minTime = Int.MAX_VALUE
        var minHeight = min
        
        // 높이의 기준 최소부터 최대까지 반복
        for (index in min..max){
        	
            // have는 가지고 있는 블럭
            var time = 0
            var have = b
            
           
            for (index1 in arr.indices){
            	// 기준이 되는 높이보다 배열의 높이가 더 작을 경우
                if (index > arr[index1]){
                	// 블럭을 쌓아야 하므로, 시간 소요값을 더하기
                    // 가지고 있는 블럭에서 사용된 블럭 개수 빼주기
                    time += index - arr[index1]
                    have -= index - arr[index1]
                }
                // 기준이 되는 높이보다 배열의 높이가 더 클 경우
                else if (index < arr[index1]){
                    time += (arr[index1]- index)*2
                    have +=  arr[index1] - index
                }
            }
            
            
            // 만약 가지고 있는 블럭을 모두 사용했다면 반복문 탈출
            // ex) 기준이 되는 높이: 3,  가지고 있는 블럭 3
            //     크기가 3이고 각각 높이가 1  2  3 이라면
            //     높이를 맞출 경우 블럭 3개를 다씀
            //     기준이 되는 높이가 4가 될 경우
            //     필요한 블럭이 5개가 되므로, 그 이전 보다 시간 소요값이 최소가 될 수 없다.
            if (have < 0)
                break
                
                
			// 시간 소요 최소값 저장
            // 시간 소요가 최소일 때 높이 저장
            if (minTime >= time){
                minTime = time
                minHeight = index
            }
        }
        println("$minTime $minHeight")
    }
}

 

 

 

 

구현하는 연습을 더욱 열심히 해야 할 것 같습니다.