[Algorithm/Kotlin] 백준 2839번 설탕 배달

 

문제 설명

설탕 배달 문제는 다음과 같습니다.
상근이는 설탕 공장에서 3kg 봉지와 5kg 봉지를 사용해 정확히 Nkg의 설탕을 배달하려고 합니다. 이때 봉지의 개수가 최소가 되도록 설탕을 나눌 방법을 찾는 문제입니다.
만약 정확히 나눌 수 없다면 -1을 반환해야 합니다.

---

문제 해결 아이디어

이 문제의 핵심은 5kg 봉지를 최대한 먼저 사용하고, 나머지를 3kg 봉지로 채우는 방법입니다. 이유는 5kg 봉지를 최대한 사용했을 때 봉지 개수가 더 줄어들 가능성이 높기 때문입니다.

로직 설계

1. 기저 조건:
   •    N<3 인 경우 설탕을 정확히 나눌 수 없으므로 -1을 반환합니다.
2. 5kg 봉지를 최대한 사용:
   •    N을 5로 나눈 몫만큼 5kg 봉지를 사용합니다.
   •    남은 설탕 무게를 계산합니다.
3. 남은 설탕 처리:
   •    남은 설탕이 3으로 나누어떨어지면, 나머지를 3kg 봉지로 채웁니다.
   •    이 경우 fiveBags+threeBags를 반환합니다.
4. 반복:
   •    5kg 봉지 개수를 하나씩 줄여가며 위 과정을 반복합니다.
   •    모든 경우를 시도했음에도 정확히 나눌 수 없다면 -1을 반환합니다.

---

구현 코드

fun sugarDelivery(n: Int): Int {
    // 1. N이 3보다 작다면 -1 반환
    if (n < 3) return -1

    // 2. 5kg 봉지 최대 사용
    for (fiveBags in n / 5 downTo 0) { // 5kg 봉지 개수를 최대값부터 줄임
        val remainingSugar = n - (5 * fiveBags) // 남은 설탕 무게 계산

        // 3. 남은 설탕이 3으로 나누어떨어질 경우
        if (remainingSugar % 3 == 0) {
            val threeBags = remainingSugar / 3 // 필요한 3kg 봉지 개수
            return fiveBags + threeBags // 최소 봉지 개수 반환
        }
    }

    // 4. 모든 경우를 시도했지만 정확히 만들 수 없는 경우 -1 반환
    return -1
}

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

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

    bw.write("${sugarDelivery(n)}")
    bw.flush()
    bw.close()
}

 

---

시간 복잡도 분석

1. 반복문:
   •    반복문은 n / 5부터 0까지 한 번씩 실행되므로 최대 반복 횟수는 (N/5)+1입니다.
2. 루프 내부 연산:
   •    각 반복에서 나머지를 계산하는 작업(O(1))이 이루어집니다.
3. 최종 시간복잡도:
   •    반복문과 내부 연산을 합쳐 시간복잡도는 O(N/5)로 단순화하면 O(N)입니다.

---

사용한 자료구조

이 코드에서는 별도의 자료구조를 사용하지 않았습니다.
다만, 다음과 같은 기본적인 Kotlin 문법이 사용되었습니다:

1. for와 downTo:
   •    5kg 봉지 개수를 최대값에서 0까지 감소시키는 반복문을 구현했습니다.
   •    이는 감소 범위를 생성하는 downTo를 활용한 Kotlin 문법입니다.
2. 간단한 수학 연산:
   •    남은 설탕의 무게를 계산하고, 나눗셈과 나머지 연산을 통해 필요한 3kg 봉지 개수를 확인했습니다.

---

해결 전략 요약

1. 5kg 봉지를 우선 사용:
   •    봉지 개수를 최소화하기 위해 5kg 봉지를 최대한 많이 사용합니다.
2. 3kg 봉지로 보완:
   •    남은 설탕이 3의 배수라면 나눌 수 있으므로 필요한 3kg 봉지 개수를 계산합니다.
3. 최소 봉지 개수 반환:
   •    조건을 만족하는 경우 최소 봉지 개수를 반환하고, 모든 경우를 시도했음에도 실패하면 -1을 반환합니다.

---

예제 실행 결과

입력	출력	설명
18	4	5kg 3개 + 3kg 1개
4	-1	정확히 나눌 수 없음
6	2	3kg 2개
9	3	3kg 3개
11	3	5kg 1개 + 3kg 2개

 

---

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

참고:

https://kotlinlang.org/api/core/kotlin-stdlib/kotlin.ranges/down-to.html 

downTo

 

https://oscarstory.tistory.com/117

[Kotlin] 코틀린의 for문 / in · .. · until · step · downTo · indices