[백준 18808번 C/C++] 스티커 붙이기
[백준 18808번 C/C++] 스티커 붙이기

https://www.acmicpc.net/problem/18808
18808번: 스티커 붙이기
혜윤이는 최근에 다양한 대회를 참여하면서 노트북에 붙일 수 있는 스티커들을 많이 받았다. 스티커는 아래와 같이 사각 모눈종이 위에 인쇄되어 있으며, 스티커의 각 칸은 상하좌우로 모두 연
www.acmicpc.net
해결전략
구현 브루스포스 Brute Force
정답 코드
#include <iostream> #include <vector> using namespace std; int n, m, k; // 노트북의 크기(n*m)와 스티커의 개수(k) int r, c; // 각 스티커의 크기(r*c) vector<vector<int>> v; // 노트북 격자 vector<vector<int>> sticker; // 각 스티커를 저장하기 위한 격자 int stickerCnt; // 스티커에 포함된 1의 개수 int answer; // 정답을 저장하기 위한 변수 // 스티커를 90도 회전시키는 함수 void Rotate() { // 회전된 스티커를 임시로 저장할 격자 temp를 생성 vector<vector<int>> temp(c, vector<int>(r)); for (int y = 0; y < r; y++) for (int x = 0; x < c; x++) temp[x][r - 1 - y] = sticker[y][x]; // 시계방향으로 90도 회전 sticker = temp; // 회전된 스티커를 저장 swap(r, c); // 스티커의 행과 열을 교환 } // 스티커를 붙일 수 있는지 확인하고 붙이는 함수 bool checkNpaste(const vector<vector<int>>& sti) { // 가능한 모든 위치에 대해 for (int i = 0; i <= n - r; i++) { for (int j = 0; j <= m - c; j++) { int cnt = 0; bool isPossible = true; vector<pair<int, int>> temp; // 스티커를 붙일 수 있는지 확인 for (int y = i; y < i + r; y++) { for (int x = j; x < j + c; x++) { if (sti[y - i][x - j] == 1 && v[y][x] == 1) { isPossible = false; break; } else if (sti[y - i][x - j] == 1 && v[y][x] == 0) { temp.push_back({ y, x }); cnt++; } } if (false == isPossible) break; } // 스티커를 붙일 수 있다면 붙이기 if (cnt == stickerCnt) { for (int i = 0; i < temp.size(); i++) v[temp[i].first][temp[i].second] = 1; return true; } temp.clear(); } } return false; // 스티커를 붙일 수 없다면 false 반환 } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); // 입력 받기 cin >> n >> m >> k; v.resize(n, vector<int>(m)); while (k--){ cin >> r >> c; sticker.resize(r, vector<int>(c)); stickerCnt = 0; // 스티커 정보 입력 받기 for (int y = 0; y < r; y++) { for (int x = 0; x < c; x++) { cin >> sticker[y][x]; if (sticker[y][x] == 1) stickerCnt++; } } int rotateCnt = 0; while (true) { // 스티커를 붙일 수 있으면 붙이고 다음 스티커로 넘어가기 if (checkNpaste(sticker)) { answer += stickerCnt; break; } else { Rotate(); // 스티커를 붙일 수 없으면 회전 rotateCnt++; } if (rotateCnt == 4) break; // 4번 회전했는데도 스티커를 못 붙이면 다음 스티커로 넘어가기 } sticker.clear(); } cout << answer << "\n"; return 0; }
'⭐ 코딩테스트 > 백준' 카테고리의 다른 글
[백준 1753번 C/C++] 최단경로 (0) | 2023.12.07 |
---|---|
[백준 16928번 C/C++] 뱀과 사다리 게임 (0) | 2023.12.06 |
[백준 9019번 C/C++] DSLR (1) | 2023.12.04 |
[백준 5430번 C/C++] AC (0) | 2023.12.03 |
[백준 1107번 C/C++] 리모컨 (0) | 2023.12.02 |
댓글
이 글 공유하기
다른 글
-
[백준 1753번 C/C++] 최단경로
[백준 1753번 C/C++] 최단경로
2023.12.07 -
[백준 16928번 C/C++] 뱀과 사다리 게임
[백준 16928번 C/C++] 뱀과 사다리 게임
2023.12.06 -
[백준 9019번 C/C++] DSLR
[백준 9019번 C/C++] DSLR
2023.12.04 -
[백준 5430번 C/C++] AC
[백준 5430번 C/C++] AC
2023.12.03
댓글을 사용할 수 없습니다.