[Kotlin, S5] 백준 2828번 사과 담기 게임

출처: unsplash.com

 

사과 담기 게임(2828번)

Silver 5

#구현 #그리디 알고리즘

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

 

문제 내용

 

 

문제 접근

사과를 담을 수 있는 바구니가 주어진다.

바구니의 범위 안에 정확히 사과를 넣어야 할 때, 바구니를 움직이는 최소 횟수를 구해야 한다.

바구니의 넓이가 1보다 클 수도 있다.

 

사과가 떨어지는 순서는 입력 순서대로 떨어진다.

떨어지는 위치에 바구니를 옮겨 주면 된다.

 

입력 예제 1을 예로 들어 보겠다.

5 1
3
1
5
3

5칸으로 나뉘어 있는  화면에 길이가 1인 바구니가 있을 때, 사과가 1 -> 5 -> 3의 위치에서 떨어질 때, 오른쪽 또는 왼쪽으로 바구니를 움직여 사과를 모두 담을 수 있는 최솟값을 구해야 한다.

 

스크린에 따라서 가장 왼쪽을 1, 가장 오른쪽을 5를 처음에 바구니는 무조건 위치 1에서 시작한다.

처음의 1은 처음 위치 1 그대로라 움직이지 않는다.

5의 경우는 오른쪽으로 4칸 움직여 준다.

3의 경우는 왼쪽으로 2칸 움직여 준다.

그래서 정답은 6개가 된다.

 

바구니를 어떤 방향으로 움직이게 할지가 중요하다.

바구니를 오른쪽으로 움직였을 때랑, 왼쪽으로 움직일 때에서 더 적은 case를 더해주면 된다.

 

 

문제 해결 코드

import java.io.BufferedReader
import java.io.InputStreamReader

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val (size, basket) = readLine().split(" ").map { it.toInt() }
    val apples = readLine().toInt()

    var basketFront = 1
    var basketBack = basket
    var answer = 0
    for (i in 0 until apples) {
        val fallingLocation = readLine().toInt()

        if (fallingLocation > basketBack) {
            while (fallingLocation != basketBack) {
                basketBack++
                basketFront++

                answer++
            }
        } else if (fallingLocation < basketFront) {
            while (fallingLocation != basketFront) {
                basketFront--
                basketBack--

                answer++
            }
        }
    }

    println(answer)
}

 

문제 풀이

입력값을 입력받고 나서 basket만큼 초기 시작 부분을 1로 지정하고 바구니의 끝 부분은 바구니의 너비로 지정해 준다.

사과가 떨어질 위치에 맞게 리스트의 위치를 변경해 준다.

바구니를 앞으로 옮길 때와 뒤로 옮길 때를 각각 구현해 준다.바구니를 옮길 때는 양 끝의 값을 뺐다가 반대 방향에 넣어 주는 방식이다.스크린을 벗어나면 안 되기 때문에 while문에 조건을 추가해 준다. 

 

 

문제 해결 과정

처음에는 deque를 쓰려고 했다가 get이 안 돼서 mutableList로 구현해 주었다.

바구니를 앞 또는 뒤로 이동해야 하는 경우를 잘 확인해야 한다.