백준: Class 3 ③ - 6064, 7576, 7569, 7662

</br> 클래스 3 계속 계속
</br>

6064: 카잉 달력

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

    while( t-- ){
        int n, m, x, y;
        cin >> m >> n >> x >> y;
        int lcm = m*n/gcd(m, n);
        if( m > n ){
            int i = 0;
            for( ; i*m+x <= lcm; i++){
                int t = (i*m + x) % n;
                if( t == y || (y == n && t == 0) ) break;
            }
            if( i*m+x > lcm ) cout << -1 << '\n';
            else cout << i*m + x << '\n';
        }
        else{
            int i = 0;
            for( ; i*n+y <= lcm; i++){
                int t = (i*n + y) % m;
                if( t == x || (x == m && t == 0) ) break;
            }
            if( i*n+y > lcm ) cout << -1 << '\n';
            else cout << i*n + y << '\n';
        }
    }

예제에서 <10, 12>를 주는데, <10:12>가 마지막인 60번째 해라니 마지막은 최소공배수겠구나 싶어서 종료 조건을 이걸로 했다.

ex) <M, N> = <10, 12>, <x, y> = <3, 9>
답을 a라고 하면
a%10 = 3
a%12 = 9
a = 10p + 3 = 12q + 9

10과 12 중 큰 걸로 for문을 돌리면 횟수가 더 적을 거임
(i*12 % 10 == 3인지 확인)

</br>

7576: 토마토

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

방법 1.

    queue< pair<int, int> > q[2];
    int zeros = 0;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> mmap[i][j];
            if( mmap[i][j] == 1 ) q[0].push(make_pair(i, j));
            else if( mmap[i][j] == 0 ) zeros++;
        }
    }
    int d = 1, now = 0, chk = 0;
    while( q[0].size() || q[1].size() ){
        int x = q[now].front().first;
        int y = q[now].front().second;
        q[now].pop();
        if( mmap[x][y] < 1 ) continue;
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if( -1 < nx && nx < n && -1 < ny && ny < m && mmap[nx][ny] == 0 ){
                 q[1-now].push(make_pair(nx, ny));
                 mmap[nx][ny] = d;
                 chk++;
            }
        }
        if( q[now].size() == 0 ){
            d++;
            now = 1-now;
        }
    }
    if( zeros == chk ) cout << d-2 << endl;
    else cout << -1 << endl;

중요한 건 그냥 bfs처럼 하면 안 되고, 1인 곳에서 모두 동시에 증가해야 한다는 거다.

ex)
0 0 0 0 0 0  0 0 0 0 0 0
0 0 0 0 0 0  0 0 0 0 0 0
0 0 0 0 0 0  0 0 0 0 0 1
0 0 0 0 0 1  0 0 0 0 1 1

0 0 0 0 0 0  0 0 0 0 0 3
0 0 0 0 0 2  0 0 0 0 3 2
0 0 0 0 2 1  0 0 0 3 2 1
0 0 0 2 1 1  0 0 3 2 1 1
이렇게


그냥 bfs하면 이렇게 됨.
0 0 0 0 0 0
0 0 0 0 0 2
0 0 0 0 2 1
0 0 0 3 1 1 
(3,5) 탐색 후 날짜가 지났는데 (4,4)를 탐색하러 가기 때문

그래서 queue를 두 개 사용하기로 했다.

1. 현재 위치에서 닿는 토마토들을 1번 큐에 넣는다.
2. 이후 1번 큐가 빌 때까지 그 큐 안은 같은 날짜로 탐색한다. 1번 큐에서 탐색한 토마토들은 0번 큐에 넣는다.
3. 1번 큐가 비면 0번 큐를 탐색한다. 반복 반복

처음 입력 받을 때 0의 개수를 세서 zeros에 저장하고, 탐색한 0의 개수가 zeros보다 작으면 -1을 출력한다.
</br>

방법 2.

지금 포스트 쓰면서 보니 큐 두 개 안 쓰고 그냥 mmap[nx][ny] = mmap[x][y]+1로 dp처럼 해도 됬겠네 헉

</br>

그리고 자매품 또 토마토 문제

7569: 토마토

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

        for(int i = 0; i < 2; i++){
            int nz = z + dz[i];
            if( -1 < nz && nz < h && mmap[nz][x][y] == 0 ){
                 q[1-now].push(make_tuple(nz, x, y));
                 mmap[nz][x][y] = d;
                 chk++;
            }
        }

pair를 tuple로 바꿔 주고, 세로축 탐색도 추가해 주면 된다.
문제만 보면 더 어려운데도 정답률이 7576: 토마토보다 높다ㅋㅋ 좀만 바꿔 주면 돼서
</br>

7662: 이중 우선순위 큐

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

    while( t-- ){
        int k;
        cin >> k;
        multiset<int> ms;
        while( k-- ){
            char c;
            int m;
            cin >> c >> m;

            if( c == 'I' ) ms.insert(m);
            else{
                if( ms.size() == 0 ) continue;
                if( m == 1 ) ms.erase(--ms.end());
                else ms.erase(ms.begin());
            }
        }
        if( ms.size() == 0 ) cout << "EMPTY\n";
        else cout << *(--ms.end()) << ' ' << *(ms.begin()) << '\n';
    }

양쪽을 볼 수 있는 우선순위 큐가 필요한데, 그게 안 되니 값을 넣을 때마다 계속 정렬이 되는 걸 생각하고 multiset을 쓰기로 했다.
set은 원래 정렬된 값으로 중복을 없애 주는데, multiset은 거기서 중복이 허용되니까 그냥 .begin()은 가장 작은 거, .end()-1은 가장 큰 거다.
</br>

---

클래스 문제 풀이가 더 재밌는 것 같다
문제 난이도도 섞여 있고
</br>