백준 [17822] 원판 돌리기

문제 출처 : https://www.acmicpc.net/problem/17822 

 

2019 하반기 문제라고 해서 한번 풀어보았다. 이 문제는 시키는 대로 잘 구현해서 풀었다.

 

다른사람은 이런 시뮬레이션에 BFS를 함께 사용하여 푸는 경우도 봤지만, 필자는 그저 시키는대로 하나하나 확인하며 해결하였다.

 

문제는 이 문제에서 회전 후, 바뀌는게 없으면 전체 수의 평균값을 가지고 +1 혹은 -1 을 하는 경우에서 평균과 같은 값이면 그대로 두어야 하는것을 잘못하여 하루종일 걸렸다... 이걸 찾는대도 오래걸렸다...

문제에서 크다와 작다로 표기되어 있는데.. 암튼 같은 경우에는 그대로 두면 된다.

그리고 가로, 즉 한 원에 들어있는 수가 m개라는걸... 다 풀고 보았다. 4개로만 되어있길래 4개를 기준으로 풀었었다.. 문제를 제대로 읽자!

 

먼저 회전을 구현한다. 메모리를 좀 낭비하며 구현하였다. 다른 괜찮은 방법이 있겠지만 급하게 푸느라 나머지 연산을 사용해 임시 배열에 옮길 값을 원본 배열에 복사하였다. 그 함수는 r(), r2() 함수이다.

 

회전했으면 지울 수가 있는지 체크한다. chk() 함수이다. 4가지 경우를 따져주면 된다. 

for문과 dx[4]={1,0,-1,0}, dy[4]={0,1,0,-1} 로 상하좌우로 생각하여 간결하게 할 수 있는걸 다 풀고 알았다. 여기서는 인덱스가 0일때 1과 m-1 이고 m-1일때, 0과 m-2 로 처음과 끝 위치만 잘 지정해주자. 그리고 이것을 수행했다는 것은 평균을 구할 일이 없다라는 체크를 해두자. chk2변수이다.

아 필자는 시계방향으로 12시를 인덱스 0으로 시작하여 순서를 정했다.

 

그다음, 지울 수가 없다면 남아있는 값들의 합으로 평균을 구하고 문제의 조건대로 각 값들을 변경시켜준다. 그렇게 t번 수행한다. 

 

그러면 답을 쉽게 구할수 있다. 아래의 코드를 참조하자. 

 

 

 

 

 

 

#include<stdlib.h>
#include<iostream>
#include<string.h>
#include<string>
#include<math.h>
#include<algorithm>
#include<stack>
#include<queue>
#include<set>
#include<iterator>
#include<deque>
#include<map>
 
using namespace std;
 
int n, m, t, x, d, k, ans,chk2;
int arr[55][55],Map[55][55];
 
void r(int a) {
    int tmp[55] = { 0 };
    for (int i = 0; i < m; i++) tmp[(i + k) % m] = arr[a][i];
    for (int i = 0; i < m; i++) arr[a][i] = tmp[i];
}
 
void r2(int a) {
    int tmp[55] = { 0 };
    for (int i = 0; i < m; i++) tmp[i] = arr[a][(i + k) % m];
    for (int i = 0; i < m; i++) arr[a][i] = tmp[i];
}
 
void chk(int a, int b, int c) {
    //cout << arr[a][b] << " ";
    int bb1 = b + 1, bb2 = b - 1, aa1 = a + 1, aa2 = a - 1;
    if (b + 1 >= m) bb1 = 0;
    else if (b - 1 <= -1) bb2 = m - 1;
    if (arr[a][b] == arr[a][bb1]) Map[a][b] = Map[a][bb1] = 1,chk2=1;
    else if (arr[a][b] == arr[a][bb2]) Map[a][b] = Map[a][bb2] = 1,chk2=1;
    else if (arr[a][b] == arr[aa1][b]) Map[a][b] = Map[aa1][b] = 1,chk2=1;
    else if (arr[a][b] == arr[aa2][b]) Map[a][b] = Map[aa2][b] = 1,chk2=1;
}
 
int main()
{
    cin >> n >> m >> t;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%d", &arr[i][j]);
        }
    }
    while (t--) {
        cin >> x >> d >> k;
        for (int i = x; i <= n; i = i + x) {
            if (d == 0) r(i);
            else r2(i);
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < m; j++) {
                if (arr[i][j] != -1){
                    chk(i, j, 0);
                }
            }
            //cout << endl;
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < m; j++) {
                if (Map[i][j] == 1) {
                    arr[i][j] = -1;
                }
                Map[i][j] = 0;
            }
        }
        //printf("%d\n ", chk2);
        if (chk2 == 0) {
            double avg = 0.0, num = 0;
            for (int i = 1; i <= n; i++) {
                for (int j = 0; j < m; j++) {
                    if (arr[i][j] != -1) num++, avg = avg + arr[i][j];
                }
            }
            //cout << avg << endl;
            for (int i = 1; i <= n; i++) {
                for (int j = 0; j < m; j++) {
                    if (arr[i][j] != -1) {
                        if (arr[i][j]*num < avg) arr[i][j] = arr[i][j] + 1;
                        else if(arr[i][j] * num > avg) arr[i][j] = arr[i][j] - 1;
                    }
                }
            }
        }
        chk2 = 0;
    }
    //r(1);
    //for (int i = 0; i < 4; i++) printf("%d ", arr[1][i]);
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < m; j++) {
            if (arr[i][j] != -1) ans = ans + arr[i][j];
    printf("%d", ans);
    return 0;
}