Koala - 11기/기초 알고리즘 스터디

[백준 / C++] 2828: 사과 담기 게임

님남누 2023. 7. 21. 17:17

문제

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

 

2828번: 사과 담기 게임

상근이는 오락실에서 바구니를 옮기는 오래된 게임을 한다. 스크린은 N칸으로 나누어져 있다. 스크린의 아래쪽에는 M칸을 차지하는 바구니가 있다. (M<N) 플레이어는 게임을 하는 중에 바구니를

www.acmicpc.net


문제 설명

하늘에서 사과가 떨어진다. 바구니로 사과를 받아내야 하는데, 사과를 받기 위해서 바구니를 몇 번 움직이는 지 출력하면 된다. 단, 움직인 횟수는 최솟값으로 출력한다.


코드

#include <iostream>
#include <vector>

using namespace std;

int boxPosLeft, boxPosRight;

int main() {
    int N, M, J; cin >> N >> M >> J;
    int move = 0;
    boxPosLeft = 1, boxPosRight = M;

    vector <bool> apple(J, false);

    for (int i = 0; i < J; i++) {
        int applePos; cin >> applePos;

        apple[applePos - 1] = true;

        while (apple[applePos - 1]) {
            if (boxPosLeft <= applePos && applePos <= boxPosRight) {
                apple[applePos - 1] = false;
            }

            else {
                if (applePos < boxPosLeft) {
                    boxPosLeft -= 1, boxPosRight -= 1;
                    move++;
                }

                else {
                    boxPosLeft += 1, boxPosRight += 1;
                    move++;
                }
            }
        }
    }

    cout << move << '\n';
}

코드 설명

vector STL을 사용해 사과가 떨어지는 위치의 인덱스에 [ true | false ] 로 표시했다.

바구니의 왼쪽과 오른쪽 좌표를 지정해줬다. 초기값으로 왼쪽은 1을, 오른쪽은 입력값 M으로 두었다.

사과의 위치를 입력받으면 vector 내에서 (해당 위치 - 1)의 값을 true로 바꿔 사과의 위치를 저장했다.

그 후 사과의 위치에 있는 값이 false가 될 때까지 바구니의 왼쪽, 오른쪽 좌표를 바꿔준다.

바구니의 왼쪽, 오른쪽 좌표 내에 사과의 위치가 있으면 값을 true로 바꾸고

왼쪽 좌표보다 사과의 위치가 낮은 값을 가지면 바구니의 좌, 우 좌표 - 1을

오른쪽 좌표보다 사과의 위치가 높은 값을 가지면 바구니의 좌, 우 좌표 + 1을 해준다.

최종적으로 움직인 횟수를 출력하면 된다.


여담

티어가 높은 문제를 풀어볼 때마다 코드를 더 짧게 써볼 수 있을까, 시간이나 공간복잡도를 절약하는 방법이 있을까 고민하게 된다. 6개월 전에 풀었을 때보다 1/3이나 코드 길이를 줄였는데 질문 게시판을 찾아보니까 더 짧은 코드들도 있는 것 같아서 나는 아직 부족하다는 것을 느끼던 문제였다. 더 노력해서 이후에 골드, 플래티넘 문제를 풀 때 효율이 높은 코드를 작성할 수 있게 실력을 길러야겠다.