백준 18080 - c++

---

요약

1. 노트북 뒷면에 스티커를 붙일 거다

2. 스티커를 붙일 때 왼쪽 가장 위에 붙일 수 있다면 바로 붙인다.

3. 안되면 스티커를 90도씩 돌려가면서 계속 붙여본다.

4. 그래도 안되면 그 스티커는 버린다.

5. 마지막에 스티커를 붙인 총넓이를 구한다.

---

아이디어

1. 스티커를 붙일 수 있는지 한 번씩 모든 좌표에서 확인해봐야 한다. 노트북 배열을 돌면서 로직을 구성한다.

2. 붙일 수 있다면 붙인다.

3. 안되면 스티커를 돌려야 한다.

 

---

구현

1. 스티커를 돌리는 함수

void rotate(){
  int tmp[12][12];

  for(int i =0; i < r; ++i)
    for(int j =0; j < c; ++j)
      tmp[i][j] = sticker[i][j];
  
  for(int i =0; i < c; ++i)
    for(int j =0; j < r; ++j)
      sticker[i][j] = tmp[r-1-j][i];

  swap(r, c);
}

이 문제를 풀며 얻은 것 중 가장 값진 지식일 것 같다.... rotate

 

2. 스티커를 붙이는 함수

bool paste(int x, int y){
  for(int i = 0; i < r; ++i){
    for(int j = 0; j < c; ++j){
      if(board[x+i][y+j] == 1 && sticker[i][j] == 1)
        return false;
    }
  }

  for(int i = 0; i < r; ++i){
    for(int j =0; j < c; ++j){
      if(sticker[i][j] == 1)
        board[x+i][y+j] = 1;
    }
  }
  return true;
}

노트북 배열을 돌며 좌표를 받아오고 거기서부터 스티커를 붙여 본다 만약 붙이지 못하면 return false

만약 return 되지 않고 끝까지 잘 수행되었다는 것은 스티커를 붙일 수 있다는 말이니

실제로 스티커를 붙인다. 그리고 return True 한다

 

3. 노트북 배열을 좌표마다 스티커를 붙일 수 있나 확인

for(int rot = 0; rot < 4; ++rot){
      bool isOk = false;
      for(int x =0; x <= n-r; ++x){
        if(isOk) break;
        for(int y =0; y <= m-c; ++y){
          if(paste(x, y)){
            isOk = true; 
            break;
          }
        }
      }
      if(isOk) break;
      rotate();
    }

pastable 함수에서 true를 받아 왔다면 isOk를 True로 바꾸고 진행한다. 계속 break... break 되면서 마지막 for문 탈출하고 다음 스티커 입력으로 넘어간다.

 

---

전체 로직

 

#include <bits/stdc++.h>

using namespace std;
void init(){
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
}

int n,m,k;
int r, c;
int board[42][42];
int sticker[12][12];

void rotate(){
  int tmp[12][12];

  for(int i =0; i < r; ++i)
    for(int j =0; j < c; ++j)
      tmp[i][j] = sticker[i][j];
  
  for(int i =0; i < c; ++i)
    for(int j =0; j < r; ++j)
      sticker[i][j] = tmp[r-1-j][i];

  swap(r, c);
}

bool paste(int x, int y){
  for(int i = 0; i < r; ++i){
    for(int j = 0; j < c; ++j){
      if(board[x+i][y+j] == 1 && sticker[i][j] == 1)
        return false;
    }
  }

  for(int i = 0; i < r; ++i){
    for(int j =0; j < c; ++j){
      if(sticker[i][j] == 1)
        board[x+i][y+j] = 1;
    }
  }
  return true;
}

int main()
{
  init();
  cin >> n >> m >> k;
  while(k--){
    cin >> r >> c;
    for(int i =0; i < r; ++i)
      for(int j =0; j < c; ++j)
        cin >> sticker[i][j];

    for(int rot = 0; rot < 4; ++rot){
      bool isOk = false;
      for(int x =0; x <= n-r; ++x){
        if(isOk) break;
        for(int y =0; y <= m-c; ++y){
          if(paste(x, y)){
            isOk = true; 
            break;
          }
        }
      }
      if(isOk) break;
      rotate();
    }
  }

  int ans = 0;
  for(int i =0; i < n; ++i){
    for(int j =0; j < m; ++j){
      ans += (board[i][j]);
    }
  }
  cout << ans;
  return 0;
}

 

---

문제를 풀며

처음에 문제를 보고 이렇게 해야겠다는 계획은 잡혔다. 하지만 배열을 어떻게 돌리는가.... 이 부분이 가장 어려웠다.

처음엔 답지를 봤고, 다음날 다시 풀어봤다, 그게 오늘이다. 하지만 쉽지 않았다. 또 답지를 봤고 그때 답지를 보고 그냥 넘겼던 부분이 이해가 되었다. 

 

내가 생각했을때 이번 문제를 풀며 얻은 가장 큰 수확은 배열을 돌리는 방법 그리고 연속된 for문을 나오는 방법이 아닐까 싶다.

요즘 시뮬레이션 문제들을 푸는데 정말 힘들다... 도저히 어떤 아이디어로 풀어야 될지 모르는 문제도 많고 생각은 했다 해도 내가 맞는지 틀리는지도 모른 채 코드가 한없이 길어지는 문제.....

하지만 이렇게 어려워야 공부이고  모르는 건 배운다는 마인드로 임하자 오늘도 많은 아이디어 배우고 갑니다

 

---

참고 : https://blog.encrypted.gg/948

[실전 알고리즘] 0x0D강 - 시뮬레이션