공부흔적

문제 링크

풀이 )

  미세먼지 확산 전 격자판을 a 배열에 저장하고, 변화량을 b 배열에 저장했다. (a 배열에 모두 저장하는 경우, 변화가 순차적으로 일어나는게 아니기 때문에 불가능했다.)

  b 배열의 경우 확산이 일어날 수 있는 방향(벽이 아니고, 공기청정기가 아닌 방향)의 개수에 따라 각 방향에 1/5에 해당되는 값을 더해주고, 해당 칸의 값에 1/5를 빼주었다.

  이후 공기청정기의 윗부분 순환과 아랫부분 순환을 구현해준 후, 마지막으로 모든 칸의 미세먼지 양을 더해준다.

#include <iostream>
#include <cstring>

using namespace std;

int r, c, t;
int cx1, cx2;
int a[50][50];
int b[50][50];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

void diffu(int x, int y){
    for(int i = 0; i < 4; ++i){
        int xx = x+dx[i];
        int yy = y+dy[i];
        if(xx < 0 || xx >= r || yy < 0 || yy >= c)
            continue;
        if((xx == cx1 || xx == cx2) && yy == 0)
            continue;
        b[xx][yy] += a[x][y]/5;
        b[x][y] -= a[x][y]/5;
    }
}

void airCleaner1(int cx){
    for(int i = cx-1; i > 0; --i){
        if(cx == 1)
            break;
        a[i][0] = a[i-1][0];
    }
    for(int i = 0; i < c-1; ++i)
        a[0][i] = a[0][i+1];
    for(int i = 0; i < cx; ++i)
        a[i][c-1] = a[i+1][c-1];
    for(int i = c-1; i > 1; --i)
        a[cx][i] = a[cx][i-1];
    a[cx][1] = 0;
}

void airCleaner2(int cx){
    for(int i = cx+1; i < r-1; ++i){
        if(cx == r-2)
            break;
        a[i][0] = a[i+1][0];
    }
    for(int i = 0; i < c-1; ++i)
        a[r-1][i] = a[r-1][i+1];
    for(int i = r-1; i > cx; --i)
        a[i][c-1] = a[i-1][c-1];
    for(int i = c-1; i > 1; --i)
        a[cx][i] = a[cx][i-1];
    a[cx][1] = 0;
}

int main(void){
    cin >> r >> c >> t;
    for(int i = 0; i < r; ++i)
        for(int j = 0; j < c; ++j){
            cin >> a[i][j];
            if(a[i][j] == -1 && a[i-1][j] == -1){
                cx1 = i-1;
                cx2 = i;
            }
        }

    while(t--){
        memset(b, 0, sizeof(b));
        for(int i = 0; i < r; ++i)
            for(int j = 0; j < c; ++j)
                if(a[i][j])
                    diffu(i, j);
        for(int i = 0; i < r; ++i)
            for(int j = 0; j < c; ++j)
                a[i][j] += b[i][j];
        airCleaner1(cx1);
        airCleaner2(cx2);
    }

    int ans = 0;
    for(int i = 0; i < r; ++i)
        for(int j = 0; j < c; ++j)
            if(a[i][j] != -1)
                ans += a[i][j];

    cout << ans << '\n';
}

주의 )

  순환 시 4방향에 따른 반복문 내 반복 횟수

문제 링크

풀이 )

  문제를 풀기에 앞서 주사위를 어떻게 표현할지를 생각해봐야한다.

  주사위의 삼면을 정하면 나머지 삼면은 고정되기 때문에 윗면, 오른쪽면, 앞면을 각각 diceU, diceR, diceF로 설정했다.

(아랫면, 왼쪽, 뒷면은 각각 5-diceU, 5-diceR, 5-diceF(눈의 수 1~6이 아닌 인덱스 0~5로 이루어져있기 때문에))

  동, 서, 남, 북에 대해서 순서대로 구현을 했다. (이동에 앞서 바깥으로 이동시키는 경우 해당 명령어를 무시한다.)

• 동쪽 이동: 윗면이 오른쪽면으로 가고, 왼쪽면이 윗면으로 간다.
• 서쪽 이동: 윗면이 왼쪽면으로 가고, 오른쪽면이 윗면으로 간다.
• 남쪽 이동: 윗면이 앞면으로 가고, 뒷면이 윗면으로 간다.
• 북쪽 이동: 윗면이 뒷면으로 가고, 앞면이 윗면으로 간다.

이후 지도를 확인하여

• 0인 경우 주사위 밑면(dice[5-diceU])의 값을 지도 칸에 저장하고
• 0이 아닌 경우 지도의 값을 주사위 밑면에 저장하고, 해당 지도 칸의 값을 0으로 만든다.

마지막으로 주사위의 윗면의 수(dice[diceU])를 출력한다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<vector<int>> map;
int dice[6] = {0, };
int diceU = 0, diceR = 2, diceF = 4;
int x, y;

void move_print(void){
    if(map[x][y]){
        dice[5-diceU] = map[x][y];
        map[x][y] = 0;
    }
    else
        map[x][y] = dice[5-diceU];
    cout << dice[diceU] << '\n';
}

int main(void){
    int n, m, k;
    cin >> n >> m >> x >> y >> k;
    for(int i = 0; i < n; ++i){
        vector<int> tmp;
        for(int j = 0; j < m; ++j){
            int cell;
            cin >> cell;
            tmp.push_back(cell);
        }
        map.push_back(tmp);
    }

    while(k--){
        int com;
        cin >> com;

        if(com == 1){
            if(y == m-1)
                continue;
            y++;
            swap(diceU, diceR);
            diceU = 5-diceU;
        }
        else if(com == 2){
            if(y == 0)
                continue;
            y--;
            swap(diceU, diceR);
            diceR = 5-diceR;
        }
        else if(com == 3){
            if(x == 0)
                continue;
            x--;
            swap(diceU, diceF);
            diceF = 5-diceF;
        }
        else{
            if(x == n-1)
                continue;
            x++;
            swap(diceU, diceF);
            diceU = 5-diceU;
        }
        move_print();
    }
    return 0;
}

주의 )

- 문제에서 주어지는 좌표 x, y의 순서에 유의한다. (세로, 가로)

문제 링크

풀이 )

  각 k번에 대해서 모든 톱니의 좌우 자석을 보고 옆 톱니의 회전에 따른 다른 톱니 회전 여부를 파악한다. (status)

  지정된 번호의 톱니를 확인한 후 왼쪽으로 방향으로 회전하는 톱니가 있는지 확인하고, 오른쪽 방향도 확인한다.

#include <iostream>

using namespace std;

int pow(int x, int n){
    if(n == 0){
        return 1;
    }
    else{
        return x*pow(x, n-1);
    }
}

int right(int gear){
    return gear/pow(10, 5)%10;
}

int left(int gear){
    return gear/10%10;
}

int rotation(int gear, int dir){
    if(dir == 1){
        gear = (gear/10)+(gear%10*pow(10, 7));
    }
    else{
        gear = (gear%pow(10, 7)*10)+gear/pow(10, 7);
    }
    return gear;
}

int main(void){

    int gear[4];
    cin >> gear[0] >> gear[1] >> gear[2] >> gear[3];

    int k;
    cin >> k;
    while(k--){
        int gearNum, dir;
        cin >> gearNum >> dir;
        gearNum--;

        int status[3] = {0, };
        for(int i = 0; i < 3; ++i)
            if(right(gear[i]) != left(gear[i+1]))
                status[i] = 1;

        gear[gearNum] = rotation(gear[gearNum], dir);
        int l = gearNum, r = gearNum;
        dir *= -1;
        int ldir = dir, rdir = dir;
        while(--l >= 0 && status[l] == 1){
            gear[l] = rotation(gear[l], ldir);
            ldir *= -1;
        }
        while(++r < 4 && status[r-1] == 1){
            gear[r] = rotation(gear[r], rdir);
            rdir *= -1;
        }
    }
    int res = 0;
    for(int i = 0; i < 4; ++i)
        res += gear[i]/pow(10, 7)*pow(2, i);

    cout << res << endl;
    return 0;
}

문제 링크

풀이 )

  개인적인 편의상 이차원배열에서 좌표를 [y][x]로 했다.

  먼저 뱀의 몸이 지나고 있는 자리 board를 배열로 나타내고, 사과 apple의 위치를 나타내기 위한 배열을 따로 만들었다.

  그리고 뱀의 몸을 나타내기 위한 큐 snake와 방향 회전 turn을 만들었다.

  먼저 현재 좌표(curY, curX)가 보드 안에 있는지(벽에 부딪힌지 여부) 확인한 후, 몸에 부딪혔는지 확인하여 부딪혔다면 반복문을 종료하고 결과를 출력한다.

  현재 좌표에 뱀의 머리가 있으므로 뱀에 넣어주고 board의 현재 위치를 1로 만들어준다. 그리고 현재 위치에 사과가 없다면(!apple[curY][curX]) 뱀의 꼬리, 즉 가장 먼저 들어간 원소이므로 front()에 있는 board를 0으로 만들어준다.

  사과가 있다면 사과를 먹었으므로 다시 apple[curY][curX]를 0으로 만들어준다.

  다음 회전을 기다리기 위해 회전할 초를 저장하는 next를 만들었다.

  next가 비어있는 경우 turn 큐에서 pop을 해서 몇초인지 next에 넣어주고, 어떤 방향인지 next_dir에 넣어준다.

  이후 회전하는 시간이 되면(ans == next) 방향에 맞게 회전해준다.

  dx, dy를 각각 시계방향으로 만들었기 때문에 오른쪽이면 (dir+1)%4, 왼쪽이면 (dir-1+4)%4로 해준다. 이 때 왼쪽의 경우 +4를 해주어 dir이 음이 되는 것을 방지한다.

  이후 현재의 좌표를 이동시키고 다음 반복문을 진행한다.

#include <cstdio>
#include <queue>	// queue
#include <utility>	// pair
using namespace std;

int dx[4] = {0, 1, 0, -1};
int dy[4] = {-1, 0, 1, 0};

int main(void)
{
  int n, k, l, board[101][101] = {0, }, apple[101][101] = {0, };
  char c[101] = "";
  queue<pair<int, int>> snake;
  queue<pair<int, char>> turn;

  scanf("%d%d", &n, &k);
  for(int i = 0; i < k; ++i){
    int x, y;
    scanf("%d%d", &y, &x);
    apple[y][x]++;
  }
  scanf("%d", &l);
  for(int i = 0; i < l; ++i){
    int x;
    char dir;
    scanf("%d %c", &x, &dir);
    turn.push(make_pair(x, dir));
  }

  int ans = 0, curX = 1, curY = 1, dir = 1, next = 0;
  char next_dir;

  while(1){
    // 부딪힌지 여부
    if(curX < 1 || curX > n || curY < 1 || curY > n)
      break;
    if(board[curY][curX])
      break;

    snake.push(make_pair(curY, curX));
    board[curY][curX] = 1;
    // 사과가 없을 때
    if(!apple[curY][curX] && ans){
      int tmpX, tmpY;
      tmpX = snake.front().second;
      tmpY = snake.front().first;
      snake.pop();
      board[tmpY][tmpX] = 0;
    }
    // 사과가 있을 때
    else
      apple[curY][curX] = 0;

    // 다음 회전
    if(next == 0){
      next = turn.front().first;
      next_dir = turn.front().second;
      turn.pop();
    }
    if(ans == next){
      next = 0;
      if(next_dir == 'L')
        dir = (dir+3)%4;
      else
        dir = (dir+1)%4;
    }
    ans++;
    curX += dx[dir];
    curY += dy[dir];
  }
  printf("%d\n", ans);
  return 0;
}

주의점 )

  - 좌표 범위

  - 회전