[백준] 2839번: 설탕 배달 - Kotlin[코틀린]

문제

 

2839번: 설탕 배달

 

---

풀이

 

 이 문제는 이중 반복문(3의 배수 + 5의 배수의 합)으로 해결할 수도 있지만, 효율적인 풀이를 위해 그리디 알고리즘과 DP를 이용할 수 있다.

 

- 그리디 풀이

 1. N이 5의 배수라면 답은 N/5

 2. N이 5의 배수가 아니라면 3kg 에 한 번 담고(cnt++, N -= 3) 다시 반복문을 실행한다.

 3. N이 0보다 작아지면 답은 -1

 

- dp 풀이

 N이라는 숫자를 만들기 위해서 (N - 3) + 3 또는 (N - 5) + 5 의 경우로 나눠 볼 수 있다. 그리고 N - 3 이라는 숫자 또한 ((N - 3) - 3) + 3 또는 ((N - 3) - 5) + 5 로 나눌 수 있다. 이 중에서 적은 봉지를 구해야 하기 때문에 두 경우 중에서 더 적은 숫자를 선택하면 된다. 따라서 이 문제의 점화식은 dp[N] = min(dp[N-3], dp[N-5]) 이다.

 

1. -1 로 초기화 되어 있는 dp 배열을 만들어 준다.

2. dp[3] 과 d[5] 는 1 이다.

3. 6부터 N 까지 반복문을 통해 dp 배열을 채워준다.

  1) i가 5의 배수라면 dp[i - 5] + 1

  2) i가 3의 배수라면 dp[i - 3] + 1

  3) 이 외에는 dp[i - 3] 과 dp[i - 5] 중에서 작은 값 + 1

 

---

코드

 

- 그리디

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    var num = br.readLine().toInt()
    var cnt = 0

    while(true) {
        if(num%5==0) {
            cnt += num/5
            break
        }

        cnt++
        num-=3

        if(num<0) {
            cnt = -1
            break
        }
    }

    bw.write("$cnt")
    bw.flush()
    bw.close()
    br.close()
}

 

- DP

import kotlin.math.min

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    val num = br.readLine().toInt()

    val dp = IntArray(num+1){-1}

    dp[3] = 1
    if(num>=5) dp[5] = 1

    for(i in 6 .. num) {
        if(i % 5 == 0) {
            dp[i] = dp[i - 5] + 1
        } else if(i % 3 == 0) {
            dp[i] = dp[i - 3] + 1
        } else {
            if(dp[i-3] != -1 && dp[i-5] != -1) {
                dp[i] = min(dp[i-3], dp[i-5]) + 1
            }
        }
    }

    bw.write("${dp[num]}")
    bw.flush()
    bw.close()
    br.close()
}