[20057] 마법사 상어와 토네이도

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

20057번: 마법사 상어와 토네이도

<문제>

토네이도의 이동 방향은 '좌하우상'의 반복이고, 길이는 {1, 1, 2, 2, 3, 3...}같은 형태로, 2번마다 1씩 증가하는 형태이다.

문제에 제시된 '일정한 비율'을 db로 넣어준다.

해당 db는 회전의 용이성을 이유로 일부러 5*5의 형태로 잡아두었고

토네이도의 방향이 회전할때마다 db도 같이 회전시켜주었다.

소수점 아래를 버리는 부분은 int간의 '/'연산으로 자연스레 해결되는 부분이며

알파부분에 들어가는 모래 양을 잘 계산해줘야 하는데, 식을 한 번에 묶지 말고 전개하여 계산해야 한다.
(55%로 계산하면 틀리는 거로 확인했는데, 반례 찾기도 쉽지 않아 보인다)

구현 난이도가 꽤 높은 문제였다.

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
const int power[5][5] = {
    {0, 0, 2, 0, 0},  {0, 10, 7, 1, 0}, {5, 55, 0, 0, 0},
    {0, 10, 7, 1, 0}, {0, 0, 2, 0, 0},
};
int n, ans, dy[4] = {0, 1, 0, -1}, dx[4] = {-1, 0, 1, 0};  //좌하우상
int curPower[5][5], a[501][501];
void updateAnswer(int score) { ans += score; }
int c(int base) {
    int ret = base;
    ret = ret - ((1 * base) / 100);
    ret = ret - ((1 * base) / 100);
 
    ret = ret - ((2 * base) / 100);
    ret = ret - ((2 * base) / 100);
 
    ret = ret - ((7 * base) / 100);
    ret = ret - ((7 * base) / 100);
 
    ret = ret - ((10 * base) / 100);
    ret = ret - ((10 * base) / 100);
 
    ret = ret - ((5 * base) / 100);
    return ret;
}
void f(int cy, int cx) {  //(cy,cx)==(2,2);y
    int base = a[cy][cx];
    if (base == 0) return;
    a[cy][cx] = 0;
    for (int y = -2; y <= 2; y++) {
        for (int x = -2; x <= 2; x++) {
            if (curPower[y + 2][x + 2] == 0) continue;
            int cur = 0;
            if (curPower[y + 2][x + 2] == 55)
                cur = c(base);
            else
                cur = (curPower[y + 2][x + 2] * base) / 100;
            int curY = cy + y;
            int curX = cx + x;
            if (curY < 0 || curX < 0 || curY >= n || curX >= n) {
                updateAnswer(cur);
                continue;
            }
            a[curY][curX] += cur;
        }
    }
}
void updatePower(void) {
    int i, j, temp[5][5];
    for (i = 0; i < 5; i++)
        for (j = 0; j < 5; j++) temp[i][j] = curPower[i][j];
 
    for (i = 0; i < 5; i++)
        for (j = 0; j < 5; j++) curPower[5 - j - 1][i] = temp[i][j];
    return;
}
int main(void) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    int i, j;
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++) cin >> a[i][j];
    int l = 1, y = n / 2, x = n / 2, dir = 0;
    for (i = 0; i < 5; i++)
        for (j = 0; j < 5; j++) curPower[i][j] = power[i][j];
    while (1) {
        if (y == 0 && x == 0) break;
        for (i = 0; i < 2; i++) {
            for (j = 0; j < l; j++) {
                y += dy[dir];
                x += dx[dir];
                f(y, x);
                if (y == 0 && x == 0) {
                    cout << ans;
                    return 0;
                }
            }
            updatePower();
            dir++;
            if (dir == 4) dir = 0;
        }
        l++;
    }
    cout << ans;
    return 0;
}