[백준] 17822 원판 돌리기

복기

 

그동안 나태한 나날을 보내다 오랜만에 푼 탓도 있겠지만 정말 시간을 많이 잡아먹은 문제입니다. (시간을 재진 않았지만 세 시간은 넘어간 것 같네요.)

또, 문제 푸는 방법을 다시 한 번 깨닫게 해 준 문제이기도 하죠.

 

* 문제 푸는 방법   1번 문제를 읽는다   2번 문제를 이해한다.   3번 문제를 푼다.

 

정말... 알지만 실천하기 힘든 것 같습니다. ㅠㅠ 문제를 읽기도 전에 이미 손은 자판을 치고 있고 이해는 대충한 상태로 코드를 짜다가 이상하다 싶을 때가 되서야 문제를 다시보게 되는... 항상 고쳐야하지 하고 다짐하지만 마음이 급한 탓인지, 성격이 급한 탓인지 쉽지가 않네요. 정직하게 가는 길이 지름길인 것을... -_-; 이번에도 T번의 입력만큼 회전을 모두 시키고 나서 원판의 인접한 수를 찾는 거라고 이해하고 코드를 짜다가 싸한 느낌에 문제를 다시 읽어보니 T번의 매 입력마다 원판 회전 후 인접한 수를 찾아야 하는거였죠.

 

흠... 글을 쓰기 전에는 문제 잘못읽어서 시간을 많이 날린줄 알았는데 쓰면서 다시 생각해보니 굳은 머리와 구현 능력이 부족함에도 좀 더 이쁘게 코드를 짜려했던 제 욕심이 범인이었네요.

 

우선 원판을 k번 회전시키는 부분에서부터 막혔는데 처음에 생각했던건 1번 숫자를 먼저 저장해놓고 M-1번 만큼 다음에 이번 자리에 올 숫자의 인덱스를 찾은 뒤 이동시키고 마지막엔 남는 자리에 저장해 두었던 1번 숫자를 넣어주려고 했었죠. 예를 들어, M이 5이고 원판 하나의 숫자가 { 1, 7, 3, 9, 5 } 일때, 반시계방향으로 2회 회전시켜야한다면 저장한 1번 인덱스에 올 인덱스는 3번이고 그다음은 5 < 2 < 4 그리고 M번째 마지막 4에는 저장해두었던 < 1 을 넣는것이죠.

네. 하지만 간과한 부분이 있었으니 경우에 따라 모든 숫자에 회전의 기회가 돌아가지 않을 수가 있었습니다. { 1, 2, 3, 4 } 에 CCW로 2회라면 1 < 3 < 1 < 3 < ... 이렇게 돌게 되는거죠. 결국 저대로라면 M과 k에 따라 숫자를 2개, 3개, 저장해야하는 꼴이니... 결국은 가장 쉽게 생각되는 배열 복붙으로 풀었습니다. 크기도 크지 않은데 배열을 하나 더 만들려니 왜이리 마음이 안좋은지 ㅠ.

회전시 시작 위치에(1번) 들어갈 인덱스가 3번이라면 3번부터 배열 한바퀴 돌리면서 복사한 후 나중에 그대로 붙혀넣기했습니다.

 

#pragma warning(disable : 4996)
#include <stdio.h>

int N, M, T;
int in[55][55];

void erase(int n, int m, int c) {
    if (in[n][m] != c) return;
    in[n][m] = 0;
    erase(n + 1, m, c);
    erase(n - 1, m, c);
    erase(n, (m - 1) ? m - 1 : M, c);
    erase(n, (m + 1) % (M + 1) ? m + 1 : 1, c);
}
int main(void) {
    scanf("%d %d %d", &N, &M, &T);
    for (int n = 1; n <= N; n++)
        for (int m = 1; m <= M; m++)
            scanf("%d", &in[n][m]);
    for (int t = 0; t < T; t++) {
        int x, d, k;
        scanf("%d %d %d", &x, &d, &k);
        k = d ? k : M - k;

	// 원판 회전시키기
        int cp[55] = {};
        for (int n = x; n <= N; n += x) {
            for (int m = 1; m <= M; m++)
                cp[m] = in[n][(k + m - 1) % M + 1];
            for (int m = 1; m <= M; m++)
                in[n][m] = cp[m];
        }

	// 회전 후 붙어있는 수 삭제
        int del = 0;
        for (int n = 1; n <= N; n++) {
            for (int m = 1; m <= M; m++) {
                if (in[n][m] == 0) continue;
                if (in[n][m] != in[n + 1][m] &&
                    in[n][m] != in[n - 1][m] &&
                    in[n][m] != in[n][(m - 1) ? m - 1 : M] &&
                    in[n][m] != in[n][(m + 1) % (M + 1) ? m + 1 : 1]) continue;
                del++;
                erase(n, m, in[n][m]);
            }
        }
        if (del) continue;

	// 평균내서 더하기 빼기하는 작업
        double avr = 0;
        int cnt = 0;
        for (int n = 1; n <= N; n++) {
            for (int m = 1; m <= M; m++) {
                avr += in[n][m];
                if (in[n][m]) cnt++;
            }
        }
        if (cnt != 0)
            avr /= cnt;
        for (int n = 1; n <= N; n++) {
            for (int m = 1; m <= M; m++) {
                if (in[n][m] == 0) continue;
                if (in[n][m] < avr) in[n][m]++;
                else if (in[n][m] > avr) in[n][m]--;
            }
        }
    }
    
    // 답구하기 총합
    int ans = 0;
    for (int n = 1; n <= N; n++)
        for (int m = 1; m <= M; m++)
            ans += in[n][m];
    printf("%d\n", ans);
    return 0;
}

더욱 정진해야겠습니다. :-)