[백준] (Swift) 2839번 - 설탕 배달 (수학적인 풀이 & dp풀이, 두가지 풀이 방법)

 

🟠 문제 링크

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

2839번: 설탕 배달

 

🟠 문제 풀이 방법 (1) - 수학적인 풀이 

수학적으로 접근하면 사실 굉장히 간단하게 풀린다. 첫번째 예제인 18로 예를들어보자.
"5로 막 나누다가 마지막에 3의배수가 되는지 찾아보면 최소값 찾을 수 있지않아?" 라고 생각할 수 있다. 나또한 그랬었고 ^__^ 근데 예제 5번을 보면, 11은 5kg / 5kg 하고 1kg가 남게되어서 -1을 출력하는게 아니라, 3kg / 3kg / 5kg 로 봉지를 들 수 있다. 그래서 3이라고 출력해야한다. 이런 예외사항을 보고 코드를 짜야했다.

그래서 선택한 방법은, 5의 배수인지 먼저 확인해준 뒤, 3을 배주고, 다시 5의 배수인지 확인해주고, 그래도 아니라면 또 3을 빼주고... 이 과정을 반복하면 되겠다 라고 생각했다. 

 

🔸  수학적인 풀이 정답 코드 

https://github.com/deslog/Algorithm/blob/main/Algorithm/Boj/2839_%EC%84%A4%ED%83%95%EB%B0%B0%EB%8B%AC/basic%20solution%20(math).swift

GitHub - deslog/Algorithm

var sugar = Int(String(readLine()!))!
var bag = 0

while sugar >= 3 {
    if sugar % 5 == 0 {
        bag += 1
        sugar -= 5
    } else {
        sugar -= 3
        bag += 1
    }
}

if sugar == 0 {
    print(bag)
} else {
    print(-1)
}

 

🟠 문제 풀이 방법 (2) - DP 로 풀기 (동적계획법)

사실 이 문제는 백준에서 DP 로 분류되어있다. 딱 보자마자, 바로 수학적인 풀이로 풀이가 가능해서 그냥 풀었지만, 뭔가 '연속해서 계산한다'라는 말이 명시적으로 없기 때문에 DP로 풀거라고 생각치도 못했다. (그냥 애초에 수학적인 풀이로 너무 간단하게 풀려서 DP로 풀생각조차 안했던 것 같다.)

그러다가 궁금해져서 dp 로도 풀어봤다.

점화식은 이렇게 도출된다.

i-5했을때 0 이하로 나오게 되면 index out of range 에러가 나기 때문에 dp[3]과 dp[5] 는 1을 넣어주고 시작해야한다.

그리고,,, 입력되는 n은 3부터 시작이지만, 4에대한 예외처리가 필요하다. 4를 처리하지않으면 dp[5]는 out of range 라서 컴파일 에러가 나기때문에 4일때 print(-1)해주는 처리와, dp[5]에 1을 넣어주지 않는 과정이 필요하다!! (이거 때문에 시간을 거의 20분은 버린듯, 주어진 예제말고 다른 예제도 입력해보자)

🔸 dp 풀이 정답코드

https://github.com/deslog/Algorithm/blob/main/Algorithm/Boj/2839_%EC%84%A4%ED%83%95%EB%B0%B0%EB%8B%AC/dp%20solution.swift

GitHub - deslog/Algorithm

var n = Int(String(readLine()!))!
var dp = Array(repeating: 5001, count: n+1)

if n > 2 {
    dp[3] = 1
    if n > 4{
        dp[5] = 1
    }
}

if n > 5 {
    for i in 6..<n+1 {
        dp[i] = min(dp[i-3]+1, dp[i-5]+1)
    }
}

if n == 4 {
    print(-1)
} else {
    if dp[n] > 5001 {
        print(-1)
    } else {
        print(dp[n])
    }
}