[백준] 2828번 사과담기 게임 (C++)

 

 

 

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

아이디어 및 주의사항

사과담기 게임은 특정 값이 구간내에 존재하는지를 확인하고, 바구니의 이동거리를 계산하는 문제입니다.

 

저의 경우 이 구간을 설정하는 것에 어려움을 느꼈습니다. 왜냐면 문제는 [l, r], [l, r), (l,r) 등 구간의 왼쪽 끝, 오른쪽 끝을 포함하는지를 명시하지 않았기 때문입니다. 이럴 경우 예시를 통해 구간의 양 끝을 포함할지, 미포함할지 결정하면 됩니다.

 

구간 집합을 [이상, 미만)으로 결정했다면 이것을 문제 풀 때 끝까지 이끌고 가야합니다. 갑자기 구간을 [이상, 미만)으로 정의해놓고 구간 밖을 체크할 때 [이상, 이하]로 로직을 짜다보면 값이 계속 꼬이게 됩니다. 제가 몇 시간 동안 이 문제 때문에 해결을 하지 못햇습니다.

 

[이상, 미만)으로 바구니의 경계 내부에 사과가 떨어지는지 확인해보겠습니다.

l : 바구니 왼쪽 위치, r : 바구니 오른쪽 위치 , t : 사과가 떨어지는 위치 

 

아래 사진을 보면 저는 바구니 왼쪽 위치(l) 은 1로 설정합니다. 문제에서도 바구니의 처음위치가 왼쪽 m칸을 차지한다고 했기 때문입니다.

 

구간의 집합을 [이상, 미만)으로  정의했습니다. (l <= t && t < r)로 코드를 작성합니다. 이 규칙[이상,미만)에 부합하도록 l, r 값을 조정해야합니다.

아래 예시를 통해 r 값을 결정하면 됩니다. r은 l값에 m 바구니 크기만 더하면 바구니의 경계를 나타낼 수 있습니다. 

r = l + m 이라고 정의합니다.

 

Case 1) 사과 떨어지는 위치가 바구니에 떨어지는 경우  : l <= t && t < r

1. 바구니 크기 m = 1일 때

 

l = 1, r = m + l = 1 + 1 = 2 가 됩니다. 그러면 (1 <= t && t < 2)가 되면서 사과가 정확히 바구니에 떨어진 것을 체크할 수 있습니다. 

 

바구니 크기 m = 1이고 구간 집합 l <= t < r

 

2. 바구니 크기가 m = 2 이고

구간 집합이 여전히 [이상, 미만) l <= t && t < r 일 때, 사과가 정의한 구간내에 떨어지는지 봅시다.

구간 집합은 1 <= t && t < 3,   l = 1, r = m + l = 2 + 1 = 3 

t = 2 일 때 바구니 구간 내에 떨어져 이동하지 않아도 됩니다.

 

Case 2) 사과 떨어지는 위치가 바구니 오른쪽보다 뒤에 있는 경우  : r <  t

바구니 크기 m =2 일 때 t = 5에 사과가 떨어진 후 얼만큼 이동해야할까요? 

오른쪽으로 3칸 움직이면 됩니다. 이를 코드로 어떻게 표현해야할까요?

l, r  중에 하나만 정해서 3칸 이동해야할까요? 아니면 l, r값을 둘다 3칸을 이동해야할까요? 다음에 떨어지는 사과 위치와 바구니 구간을 비교해야합니다.

 

이렇게 경우의 수가 나뉠 때 각각 천천히 생각해봅시다. 

 

1. l 값만 변경하면 된다.

 

l 값만 변경하려면 어떻게 해야할까요? l을 t - l = 5 - 1 = 4 차이값만 기존 l 에 더하면 될까요?

 

l = l + (t - l) = 1 + ( 5 - 1) = 1 + 4 = 5가 됩니다.

바구니 구간은 [5, 7) ,바구니 크기가 2가 되므로, 단순 사과가 떨어진 위치(t)와 바구니의 왼쪽 위치(l) 차이만 빼면 안됩니다. l 값을 하나만 빼주면 될 것 같습니다. 이때 l,r  값의 조정이 들어갑니다.

 

l  = l + ( t - l -1 ) = 1 + ( 5 - 1 - 1) = 1 + 3 = 4,

r은 기존에 r = m + l 로 정의했는데 올바르게 정의한 것인지 확인해봅시다.

저는 r을 2가지로 정의할 수 있다고 생각했습니다. 둘다 같은 값이 나오네요 그렇다면 원래 정의한 r = m + l 을 사용하면 되겠습니다. 굳이 코드를 변경할 필요가 없으니까요.

r = m + l = 2 + 4 = 6

r = r + ( t - l -1) = 3 +  (5 - 1 -1 ) = 3 + 3 = 6 

 

l값만 변경해도 충분히 r값이 자동으로 나옵니다. 그럼 3번 l, r 둘다 변경할 필요가 없겠다는 결론이 나옵니다.

이 차이값 (t - l- 1)를 이동 횟수에 누적해서 더하면 되겠다는 걸 결론 지을 수 있습니다.

 

이제 사과 떨어지는 위치가 바구니 왼쪽보다 먼저 있는 경우 t < l을 봅시다.

 

2. r 값만 변경하면 된다.

 

3. l, r  둘다 변경하면 된다.

 

주의사항 )  t >= r  일때도 오른쪽 이동

l = 1, r = 3 일 때 t = 3에 떨어지면 오른쪽으로 1칸 이동해야합니다.

이전 구간 정의할 때 [이상, 미만)으로 정의했습니다. r == t일 때도 고려해야합니다.

 

기존 구간 규칙(l <= t && t < r)을  l <= t && t <= r로 바꾼다면 m=2, l = 1, r = m + l = 2 + 1 = 3 이되고 t가 바구니 내에 떨어질 수 있는 곳은 t =1, 2, 3 , 3군데가 되므로 문제 의도가 틀려집니다. 

l, r 변수도 결국 기존 로직에 의해 정해진 값이라 로직이 바뀌면 l,r 의 의미도 바뀌기 때문입니다. 구간 [이상,미만)을 정하면 절대 바꾸면 안됩니다.

 

Case 3) 사과 떨어지는 위치가 바구니 왼쪽보다 먼저 있는 경우 : t < l

아래 사진을 보면 l 값만 한칸 이동하면 될 것 같습니다.

이전 l = 4, r = 6 이었습니다.

 

그러면 l = l - ( l - t- 1) = 4 - ( 4 - 3 - 1) =  4 가 나옵니다. 원하는 3이 나오지 않는 로직입니다. -1 만 하면 될 것 같습니다. 각 경우의 수마다 l, r 값을 조정해야하는 경우가 다른 것을 확인할 수 있습니다.

l = l - (l - t) = 4 - ( 4 - 3) = 4 - 1= 3 을 해주면 되겠네요. 그럼 r = m + l = 2 + 3 = 5 가 자동으로 나오고 원하는 값이 되는 걸 확인할 수 있습니다.

이 차이값 (l- t)를 이동 횟수에 누적해서 더하면 되겠다는 걸 결론 지을 수 있습니다.

 

 

 

 

전체 코드

l 값을 통해 r을 자동 결정할 수도 있고 동시에 변경해도 됩니다.

r도 같이 변경해주고 싶다면 int r = l + m 을 for문 밖에 위치하면 됩니다.

#include<bits/stdc++.h>
using namespace std;
int n, m, j, t, cnt; 

int main() {
    cin >> n >> m;
    cin >> j ;
    // [l, r) = { 1, l+ 1, ... , r -1} 
    int l = 1;
    for(int i = 0; i < j ; i++) {
        cin >> t ;
        // cout << '\n';
        int r = l + m ; // 포함
        if(l <= t && t < r) {

            // cout <<"[" << l << " : " << r << ") , " << t << "\n";
            continue;
        }
        else if( t >= r) {
            cnt += (t- r + 1) ;
            l += (t - r + 1);
            // r += (t - r + 1);
            // cout <<"[" << l << " : " << r << ") , " << t << "\n";
            // cout << "cnt = " << cnt << '\n';


        }
        else if (t < l) {
            cnt += (l- t);
            // r -= ( l - t);
            l -= (l - t);
            // cout <<"[" << l << " : " << r << ") , " << t << "\n";
            // cout << "cnt = " << cnt << '\n';


        }
    }
    
    cout << cnt << "\n";
    return 0;
}