[BOJ 9982] Frogger's For Dinner

난이도

매겨진 난이도: Bronze I

체감 난이도: Silver V + 0.2

 

태그

• Simulation (시뮬레이션)
• Brute Force (브루트 포스)

 

풀이

1. 특정 위치에서 특정 속도를 가지고 출발하는 차는, Frog와 같은 가로줄에 있을 때 어떤 위치에 있을까?

질문이 복잡해보이지만, 결국 "어떤 줄에서 출발하면 Frog가 이 차에 치이게 될까?" 를 찾아보는 것입니다.

 

\( x \)에서 출발하고, 속도가 \( v \)인 차는, 시간이 \( t \)초가 지나면 \( x + vt \)에 위치하게 됩니다.

Frog는 \( y \)번 가로줄에 \( y \)초부터 \( y+1 \)초까지 있게 되므로,

Frog와 차가 같은 줄에 놓이면, \( x + vy \)부터 \( x + v(y+1) \)까지의 위치에 있을 때 Frog가 치이게 됩니다.

 

물론 저렇게만 계산하면 범위를 넘어가게 되므로, 10으로 나눈 나머지를 계산해줘야 합니다.

 

2. 그럼 이걸 다 합쳐볼 수 있을까?

각각의 차량에 대해, \( [x + vy, x + v(y+1)] \) 구간을 체크해봅시다.

이는 저 구간 안에 있으면 Frog가 치이게 된다, 즉 Frog는 여기서 출발하면 무사히 도착할 수 없다 를 의미합니다.

 

모든 차량에 대해 위를 구하고 나면, 남은 건 무사히 도착할 수 있는 줄이 존재하는지 확인해주면 됩니다.

 

코드

복잡해 보이니까, 하나씩 분석해봅시다.

 

우선 (2번)에서 구하는 구간의 시작점을 p에 저장합니다.

그 뒤로, x (코드에서의 속도)칸을 이동해야 하니까

p+0, p+1, ..., p+x의 이동을 d라는 변수를 사용해 나타내고, 이를 토대로 chk라는 배열에 체크를 합니다.

bool chk[10];
 
void Main(){
    string st, ed; while (cin >> st){
        memset(chk, 0, sizeof(chk));
        for (int i = 0; i < 8; i++){
            for (int j = 0; j < 10; j++){
                int x; cin >> x; if (x == 0){ continue; }
                int sgn = (i < 4 ? -1 : +1);
                int p = (j + sgn*i*x +10000) % 10;
                for (int d = 0; d <= x; d++){ chk[(p + sgn*d +10)%10] = 1; }
            }
            //cout << "ROW " << i+1 << "   "; for (int j = 0; j < 10; j++){ cout << chk[j] << ' '; } cout << endl;
        }
        bool ans = 0;
        for (int i = 0; i < 10; i++){ ans |= (!chk[i]); }
        cout << (ans ? "LEFTOVER POSSUM" : "FROGGER") << endl;
        cin >> ed;
    }
}