[BOJ] 18185 라면 사기 (Small) (Swift)

문제 링크 

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

 

문제를 맞추고 나서 티어를 보고 굉장히 놀랐던 문제 ,, 

 

문제 접근 

문제를 읽었을 때, 전구와 스위치 문제랑 굉장히 비슷하다고 생각해서 비슷한 방법으로 접근하고자 했다. 

 

현재의 위치를 i 라고 한다면, 영향을 줄 수 있는 곳의 위치는 `i`, `i+1`, `i+2` 이다. 

`i`가 마지막 즈음에 도달했을 때 `i+1`과 `i+2`의 위치를 끝까지 접근하기 위해, 입력 받은 라면 개수의 배열에 0을 두 개 추가해주었다. 만약 라면 개수의 입력이 `1 1 1 0 2`라면 내가 사용하게 될 배열은 `[1, 1, 1, 0, 2, 0, 0]`이 된다. 

 

체크 1

현재 위치 `i`에 영향을 줄 수 있는 위치는 자기 자신 `i` 뿐이다. 

 

체크 2

3개를 묶어서 구매하는 것을 무조건 먼저 한다면 최소 금액이 아닐 수 있다. 

 

결론부터 말하자면 i+1 위치의 수가 i+2 위치의 수보다 크다면 2개로 묶는 것을 먼저 고려해줘야 한다. 

 

 

`2 3 2 1` 이라는 예시를 생각해보자. 

 

만약 3개를 묶어서 구매하는 것을 먼저 한다면, 아래 과정을 거쳐 금액은 20이 된다. 

1) 2 3 2 1 	// 금액 : 0
2) 0 1 0 1 	// 금액 : 2 x 7 = 14
3) 0 0 0 0 	// 금액 : 14 + (3 x 1 x 2) = 20

 

하지만 최소 금액은 19이다. 

1) 2 3 2 1 	// 금액 : 0
2) 1 2 2 1 	// 금액 : 5 x 1 = 5
3) 0 1 1 1 	// 금액 : 5 + (7 x 1) = 12
4) 0 0 0 0 	// 금액 : 12 + (7 x 1) = 19

 

 

그런데 `2 2 3 1`의 예시를 보면 3개를 묶어서 구매하는 것을 먼저했을 때 최소 금액이 된다. 

1) 2 2 3 1	// 금액 : 0
2) 0 0 1 1	// 금액 : 7 x 2 = 14
3) 0 0 0 0	// 금액 : 14 + 5 = 19

 

이 점만 이해했다면 문제를 풀 수 있다! 

 

문제 풀이 

라면을 살 때 2개로 묶어서 살 때와 3개로 묶어서 사는 경우에 대한 코드가 여러 번 나오므로 함수로 정의해주었다. 

`arr`는 입력받은 라면의 수를 담은 배열이다. 

// 2개 묶어서 살 때
func buy2(_ i: Int, _ count: Int) {
    arr[i] -= count
    arr[i+1] -= count
    answer += count * 5
}

// 3개 묶어서 살 때 
func buy3(_ i: Int, _ count: Int) {
    arr[i] -= count
    arr[i+1] -= count
    arr[i+2] -= count
    answer += count * 7
}

 

 

다시 정리하자면,

1.1 arr[i+1] > arr[i+2] 일 때 
   a. 2개를 묶어서 구매를 한다. 얼만큼? `arr[i+1] - arr[i+2]` 만큼 (근데 저 값보다 arr[i]가 더 작다면 `arr[i]`만큼 구매한다)
   b. 3개를 묶어서 구매할 수 있는 최대만큼 구매한다. 

1.2 arr[i+1] <= arr[i+2] 일 때 
   a. 3개를 묶어서 구매할 수 있는 최대만큼 구매한다. 
   b. 2개를 묶어서 구매할 수 있는 최대만큼 구매한다. 

2. 1번을 거쳤을 때 arr[i]에 남아있는 라면이 있다면 3원을 주고 구매한다.

 

 

코드를 보면 다음과 같다. 

 

1.1 arr[i+1] > arr[i+2] 일 때

// 2개씩 먼저
goodsCount = min(arr[i+1] - arr[i+2], arr[i])
buy2(i, goodsCount)

// 다음 3개씩
goodsCount = min(arr[i], arr[i+1], arr[i+2])
buy3(i, goodsCount)

 

1.2 arr[i+1] <= arr[i+2] 일 때

// 3개씩 먼저
goodsCount = min(arr[i], arr[i+1], arr[i+2])
buy3(i, goodsCount)

// 다음 2개씩
goodsCount = min(arr[i], arr[i+1])
buy2(i, goodsCount)

 

2. arr[i]에 남은 라면 모두 구매 

answer += arr[i] * 3

 

 

전체 코드 

import Foundation

let n = Int(readLine()!)!
var arr: [Int] = readLine()!.split(separator: " ").map { Int($0)! }+[0, 0] // 0 두 개 추가
var answer = 0
var goodsCount = Int.max
for i in 0..<n {
    // 2번째가 3번째보다 클 때
    if arr[i+1] > arr[i+2] {
        // 2개씩 먼저
        goodsCount = min(arr[i+1] - arr[i+2], arr[i])
        buy2(i, goodsCount)

        // 다음 3개씩
        goodsCount = min(arr[i], arr[i+1], arr[i+2])
        buy3(i, goodsCount)
    } else {
        // 3개씩 먼저
        goodsCount = min(arr[i], arr[i+1], arr[i+2])
        buy3(i, goodsCount)

        // 다음 2개씩
        goodsCount = min(arr[i], arr[i+1])
        buy2(i, goodsCount)
    }

    // 남은건 하나씩 구매
    answer += arr[i] * 3
}

print(answer)

// 2개 묶어서 살 때
func buy2(_ i: Int, _ count: Int) {
    arr[i] -= count
    arr[i+1] -= count
    answer += count * 5
}

// 3개 묶어서 살 때
func buy3(_ i: Int, _ count: Int) {
    arr[i] -= count
    arr[i+1] -= count
    arr[i+2] -= count
    answer += count * 7
}

 

아이디어가 관건인 문제인 것 같다. 생각할 수 있다면 그다지 어렵지 않은 문제.

전구와 스위치 문제를 풀었기 때문에 접근법을 생각할 수 있었고, 많이 풀어서 다양한 접근법 또는 풀이법을 익히는 것이 답이라는 생각이 들었다 ..