BOJ 17822 : 원판 돌리기 - C++

원판 돌리기

코드

#include <cstdio>
#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <set>
#include <deque>
#include <numeric>
#include <map>
#define ll long long
using namespace std;
// 1253 ~ 0304
int N,M,T,ans;
deque<pair<int,bool>> cycle[55];

int DirCntCalc(int dir, int cnt)
{
    if(dir == 0) return cnt;
    /* 개수가 고정이 아니기때문에 M-cnt로 해야한다 */
    return M-cnt;
}
bool checkPos(int i)
{
    if(i<1 or i>N) return false;
    return true;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> M >> T;
    for(int i=1;i<=N;i++)
    {
        for(int j=1;j<=M;j++)
        {
            int a;
            cin >> a;
            cycle[i].push_back({a, false});
        }
    }
    for(int n=1;n<=T;n++)
    {
        int ch, dir, cnt;
        cin >> ch >> dir >> cnt;
        /* 원판 회전 */
        int res = DirCntCalc(dir,cnt); // 모두 시계방향으로 계산하기 위함
        for(int size=ch;size<=N;size+=ch)
        {
            for(int i=0;i<res;i++)
            {
                int tmp = cycle[size].back().first;
                cycle[size].pop_back();
                cycle[size].push_front({tmp, false});
            }
        }
        /* 인접한 수가 같은것이 있는지 검사 */
        bool del = false;
        int sum = 0;
        int size = 0;
        for(int i=1;i<=N;i++)
        {
            for(int j=0;j<M;j++)
            {
                int cur = cycle[i][j].first;
                if(cur == -1e9) continue;
                if(checkPos(i+1) and cur == cycle[i+1][j].first){
                    cycle[i+1][j].second = true;
                    cycle[i][j].second = true;
                    del = true;
                }
                if(checkPos(i-1) and cur == cycle[i-1][j].first){
                    cycle[i-1][j].second = true;
                    cycle[i][j].second = true;
                    del = true;
                }
                int nj = j+1;
                if(nj >=M) nj -= M;
                if(cur == cycle[i][nj].first){
                    cycle[i][nj].second = true;
                    cycle[i][j].second = true;
                    del = true;
                }
                nj = j-1;
                if(nj < 0) nj += M;
                if(cur == cycle[i][nj].first){
                    cycle[i][nj].second = true;
                    cycle[i][j].second = true;
                    del = true;
                }
            }
        }
        /* true로 체크된 수 삭제하기 */
        for(int i=1;i<=N;i++)
        {
            for(int j=0;j<M;j++)
            {
                if(cycle[i][j].first == -1e9) continue;
                if(cycle[i][j].second == true)
                    cycle[i][j].first = -1e9;
                if(cycle[i][j].first != -1e9){
                    sum += cycle[i][j].first;
                    size++;
                }
            }
        }
        /* 인접한 것이 없어서 숫자를 지우지 않았다면 */
        if(del == false)
        {
            double avg = sum/(double)size;
            sum=0;
            for(int i=1;i<=N;i++)
            {
                for(int j=0;j<M;j++)
                {
                    if(cycle[i][j].first == -1e9) continue;
                    if(cycle[i][j].first > avg) cycle[i][j].first--;
                    else if(cycle[i][j].first < avg) cycle[i][j].first++;
                    sum += cycle[i][j].first;
                }
            }
        }
        ans = sum;
    }
    cout << ans;
    return 0;
}
  • 핵심
    • 원판회전할 때 dir(방향)횟수(cnt)를 받아서 무조건 시계방향으로 변환하면 반시계방향 구현하지 않아도 됨
      --> reverseDir에서 주의할 것M-cnt로 해야한다! (1 CycleM에따라 바뀌기 때문에)
    • 인접한 수가 같은것이 있는지 검사하는 과정에서 바로 값바꾸면 안된다
      --> 바로 인접한 값들을 바꾸면 다음 검사영향을 끼칠 수 있음
      --> bool 변수체크만 하고 한번에 값변경해야 한다!!!
  • 오래걸린 이유
    : 인접한 수가 같은것이 있는지 검사하면서 값을 바로 갱신했더니 다음 수행영향을 끼쳐서 오작동
    --> 값을 수정할 때 다음 반복문영향을 주는지확인하자.....
    --> 안전하게 bool변수체크해서 한번에 변경 하자

좋은 웹페이지 즐겨찾기