백준 17822 : 원판 돌리기

원판 돌리기 성공

 

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

512 MB

13924

4941

3094

31.825%

문제

반지름이 1, 2, ..., N인 원판이 크기가 작아지는 순으로 바닥에 놓여있고, 원판의 중심은 모두 같다. 원판의 반지름이 i이면, 그 원판을 i번째 원판이라고 한다. 각각의 원판에는 M개의 정수가 적혀있고, i번째 원판에 적힌 j번째 수의 위치는 (i, j)로 표현한다. 수의 위치는 다음을 만족한다.

• (i, 1)은 (i, 2), (i, M)과 인접하다.
• (i, M)은 (i, M-1), (i, 1)과 인접하다.
• (i, j)는 (i, j-1), (i, j+1)과 인접하다. (2 ≤ j ≤ M-1)
• (1, j)는 (2, j)와 인접하다.
• (N, j)는 (N-1, j)와 인접하다.
• (i, j)는 (i-1, j), (i+1, j)와 인접하다. (2 ≤ i ≤ N-1)

아래 그림은 N = 3, M = 4인 경우이다.

원판의 회전은 독립적으로 이루어진다. 2번 원판을 회전했을 때, 나머지 원판은 회전하지 않는다. 원판을 회전시킬 때는 수의 위치를 기준으로 하며, 회전시킨 후의 수의 위치는 회전시키기 전과 일치해야 한다.

다음 그림은 원판을 회전시킨 예시이다.

1번 원판을 시계 방향으로 1칸 회전	2, 3번 원판을 반시계 방향으로 3칸 회전	1, 3번 원판을 시계 방향으로 2칸 회전

원판을 아래와 같은 방법으로 총 T번 회전시키려고 한다. 원판의 회전 방법은 미리 정해져 있고, i번째 회전할때 사용하는 변수는 xi, di, ki이다.

1. 번호가 xi의 배수인 원판을 di방향으로 ki칸 회전시킨다. di가 0인 경우는 시계 방향, 1인 경우는 반시계 방향이다.
2. 원판에 수가 남아 있으면, 인접하면서 수가 같은 것을 모두 찾는다.
   1. 그러한 수가 있는 경우에는 원판에서 인접하면서 같은 수를 모두 지운다.
   2. 없는 경우에는 원판에 적힌 수의 평균을 구하고, 평균보다 큰 수에서 1을 빼고, 작은 수에는 1을 더한다.

원판을 T번 회전시킨 후 원판에 적힌 수의 합을 구해보자.

입력

첫째 줄에 N, M, T이 주어진다.

둘째 줄부터 N개의 줄에 원판에 적힌 수가 주어진다. i번째 줄의 j번째 수는 (i, j)에 적힌 수를 의미한다.

다음 T개의 줄에 xi, di, ki가 주어진다.

출력

원판을 T번 회전시킨 후 원판에 적힌 수의 합을 출력한다.

제한

• 2 ≤ N, M ≤ 50
• 1 ≤ T ≤ 50
• 1 ≤ 원판에 적힌 수 ≤ 1,000
• 2 ≤ xi ≤ N
• 0 ≤ di ≤ 1
• 1 ≤ ki < M

예제 입력 1 복사

4 4 1
1 1 2 3
5 2 4 2
3 1 3 5
2 1 3 2
2 0 1

예제 출력 1 복사

30

원판의 초기 상태는 다음과 같다.

x1 = 2, d1 = 0, k1 = 1 2번, 4번 원판을 시계 방향으로 1칸 돌린 후	인접하면서 수가 같은 것을 모두 지운 후

예제 입력 2 복사

4 4 2
1 1 2 3
5 2 4 2
3 1 3 5
2 1 3 2
2 0 1
3 1 3

예제 출력 2 복사

22

예제 1에서 이어진다.

x2 = 3, d2 = 1, k2 = 3 3번 원판을 반시계 방향으로 3칸 돌린 후	인접하면서 수가 같은 것을 모두 지운 후

예제 입력 3 복사

4 4 3
1 1 2 3
5 2 4 2
3 1 3 5
2 1 3 2
2 0 1
3 1 3
2 0 2

예제 출력 3 복사

22

예제 2에서 이어진다.

x3 = 2, d3 = 0, k3 = 2 2, 4번 원판을 시계 방향으로 2칸 돌린 후	인접하면서 수가 같은 것이 없다. 따라서, 평균 22/6 보다 작은 수는 +1, 큰 수는 -1 했다.

예제 입력 4 복사

4 4 4
1 1 2 3
5 2 4 2
3 1 3 5
2 1 3 2
2 0 1
3 1 3
2 0 2
3 1 1

예제 출력 4 복사

0

예제 3에서 이어진다.

x4 = 3, d4 = 1, k4 = 1 3번 원판을 반시계 방향으로 1칸 돌린 후	인접하면서 수가 같은 것을 모두 지운 후

예제 입력 5 복사

4 6 3
1 2 3 4 5 6
2 3 4 5 6 7
3 4 5 6 7 8
4 5 6 7 8 9
2 1 4
3 0 1
2 1 2

예제 출력 5 복사

26

원판 돌리기

4 4 1
1 1 2 3
5 2 4 2
3 1 3 5
2 1 3 2
2 0 1
이런식으로 입력이 주어진다.
첫 4는 한 원판의 층을 기준으로 
안쪽부터 
1 1 2 3 은

    1 
 3     1
    2 
이런 원판 구조로 만들어지고
그 다음
5 2 4 2 는
      5
      1 
2 3     1 2
      2 
      4
첫 원판을 그 다음으로 감싼다.
입력을 다 받으면
           2
           3
           5
           1 
2 5 2 3     1 2 1 1 
           2 
           4
           3
           3
이렇게 된다. 
그 다음으로 주어진 입력
2 0 1 은
첫번째 주어지는 숫자인 2, 그리고 이 숫자의 배수에 해당하는 원판을 2번째 주어지는 0,1
방향으로 마지막 주어지는 숫자 1만큼 이동시키는 것이다.
그리고 따져줘야 하는 조건
원판에 수가 남아 있으면 인접하면서 수가 같은 수는 지운다.
없는 경우에는 원판에 적힌 수의 평균을 구하고 
평균보다 큰 수에서 1을 빼고 작은 수에는 1을 더한다.

인접고려조건
(i, 1)은 (i, 2), (i, M)과 인접하다.
(i, M)은 (i, M-1), (i, 1)과 인접하다.
(앞그리고 맨 끝과 인접하고)
(i, j)는 (i, j-1), (i, j+1)과 인접하다. (2 ≤ j ≤ M-1)
(중간에 있는 사람은 앞뒤로 인접)

(1, j)는 (2, j)와 인접하다.
(N, j)는 (N-1, j)와 인접하다.
(위 그리고 위라면 맨밑과 인접)
(i, j)는 (i-1, j), (i+1, j)와 인접하다. (2 ≤ i ≤ N-1)
(중간에는 위 아래)


우선 원판 돌리는 것 부터 구현해야한다.

메모

2 3 4 5 6 7
6 7 2 3 4 5

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int arr[51][51];
int N, M, K;

void roll(int x, int d, int k) {//배수,방향,칸수

    for(int i=x; i<=M; i*=x){//배수만
        if (d == 0) {//시계
            //1 1 2 3이면
            //3 1 1 2
            int copy[51];
            for (int a = 1; a <= M; a++)
                copy[a] = arr[i][a];//배열 복사

            for (int a = 1; a <= M; a++) {
                int c = a + k;
                if (c > M) c %= M;
                // 1 2 3 4 이고 k가 2일때 
                // 1->3 , 2 ->4 , 3->(5) % 4 =1, 4 ->(6)% 4 =2
                arr[i][c] = copy[a];
            }
        }
        else {//반시계
            //1 1 2 3이면
            //1 2 3 1
            int copy[51];
            for (int a = 1; a <= M; a++)
                copy[a] = arr[i][a];//배열 복사
            
            for (int a = 1; a <= M; a++) {
                int c = a - k;
                //1-3= -2, -2에다가 4를 더해주면 2
                if (c < 1) c += M;
                // 1 2 3 4 이고 k가 3일때 
                // 4 1 2 3 
                // 1<-4 , 2 <-1 , 3<-2, 4<-3
                arr[i][c] = copy[a];
            }
        }
    }
}
void adjaction() {//인접한 거 삭제 
    vector<pair<int, int>> v; //인접한 것들을 2개씩 넣어서 삭제해버린다.
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            if (arr[i][j] == 0)continue;
            if (i == 1 || i == N) {//세로부터 보자
                if (i == 1) {
                    if (arr[i][j] == arr[i + 1][j]) {
                        v.push_back({ i,j }); v.push_back({ i + 1,j });
                    }
                }
                else if (i == N) {
                    if (arr[i][j] == arr[N - 1][j]) {
                        v.push_back({ i,j }); v.push_back({ N - 1,j });
                    }
                }
            }
            else if(i>1 && i<N-1) {
                if (arr[i][j] == arr[i - 1][j]) {
                    v.push_back({ i,j }); v.push_back({ i - 1,j });
                }
                if (arr[i][j] == arr[i + 1][j]) {
                    v.push_back({ i,j }); v.push_back({ i + 1,j });
                }
            }

            if (j == 1 || j == M) {
                if (j == 1) {
                    if (arr[i][j] == arr[i][j+1]) {
                        v.push_back({ i,j }); v.push_back({ i,j+1 });
                    }
                    if (arr[i][j] == arr[i][M]) {
                        v.push_back({ i,j }); v.push_back({ i, M });
                    }
                }
                else if (j == M) {
                    if (arr[i][j] == arr[i][M-1]) {
                        v.push_back({ i,j }); v.push_back({i,M-1 });
                    }
                    if (arr[i][j] == arr[i][1]) {
                        v.push_back({ i,j }); v.push_back({ i,1 });
                    }
                }
            }
            else if (j > 1 && j < M - 1) {
                if (arr[i][j] == arr[i][j-1]) {
                    v.push_back({ i,j }); v.push_back({ i,j-1 });
                }
                if (arr[i][j] == arr[i][j + 1]) {
                    v.push_back({ i,j }); v.push_back({ i,j + 1 });
                }
            }
         }
            
    }if (!v.empty()) {
        for (int i = 0; i < v.size(); i++) {
            arr[v[i].first][v[i].second] = 0;
        }
    }
    else {
        int sum = 0, cnt = 0;
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                if (arr[i][j] > 0) {
                    cnt++;
                    sum += arr[i][j];
                }
            }
        }
        float V = float(sum) / cnt;
        cout << " 나는 평균" << V;
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                if (arr[i][j] != 0 && arr[i][j] > V) {
                    arr[i][j] -= 1;
                }
                else if (arr[i][j] != 0 && arr[i][j] < V) {
                    arr[i][j] += 1;
                }
            }
        }

    }
    

}


int main() {
    cin >> N >> M >> K;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            cin >> arr[i][j];
        }
    }
    for (int i = 0; i < K; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        roll(a, b, c);
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                cout << arr[i][j];
            }cout << endl;
        }
        adjaction();
        cout << endl << endl << "지금부터는 인접한 거 삭제한 경우!" << endl << endl;
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                cout << arr[i][j];
            }cout << endl;
        }
        cout << endl;
    }
    int SUM = 0;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            SUM += arr[i][j];
        }cout << endl;
    }
    cout << SUM;

    return 0;
}