[백준] 2839. 설탕 배달 (Kotlin)

문제 : https://www.acmicpc.net/problem/2839

2839번: 설탕 배달

 

 

풀이

import java.util.*
import kotlin.math.min

var min = 10000
var arr = Array(2000){Array(2000){0} }

fun main() = with(Scanner(System.`in`)){
    var n = nextInt()
    find(n,0,0,0)

    // 정확하게 만들 수 있는 경우가 하나도 없음
    if(min == 10000) min = -1

    println(min)
}

fun find(n: Int,x: Int,y: Int, count: Int){
    arr[x][y] = 1

    // 정확하게 배달이 끝났을 때 최소 횟수 체크
    if(n==0){
        min = min(min,count)
        return
    }

    // 정확하게 만들 수 없음
    if(n<0){
        return
    }

    // 이미 한 계산이라면 또 할필요 없음
    if(arr[x+1][y] != 1) find(n-3,x+1,y,count+1)
    if(arr[x][y+1] != 1) find(n-5,x,y+1,count+1)
}

x가 -3 연산을 한 횟수, y가 -5 연산을 한 횟수로 나누어서 배열에 방문처리 해주고

이미 한번 해본 연산(방문한 연산) 이라면 그 이후 연산은 할 필요가 없으므로 제외 해서 풀었다.

 

다른풀이

import java.util.*

fun main() = with(Scanner(System.`in`)){
    var n = nextInt()
    var count = 0

    while(true){
        if(n%5 == 0){
            println(count + n/5)
            return
        }

        if(n<=0){
            println(-1)
            return
        }
        n-=3
        count++
    }
}

풀고나서 생각해보니

그냥 5로 나눴을때 딱 떨어지는 수가 나올때까지 -3을 계속 반복해주고 그 횟수와 5로 나눈 값을 합하면 된다는 것을 깨달았다. 너무 어렵게 생각했나보다.