틀린 부분 또는 더 효율적인 접근법에 대해 피드백 주시면 감사하겠습니다!
첫째 줄에 노트북의 세로와 가로 길이를 나타내는 N(1 ≤ N ≤ 40)과 M(1 ≤ M ≤ 40), 그리고 스티커의 개수 K(1 ≤ K ≤ 100)이 한 칸의 빈칸을 사이에 두고 주어진다.
그 다음 줄부터는 K개의 스티커들에 대한 정보가 주어진다. 각 스티커는 아래와 같은 형식으로 주어진다.
먼저 i번째 스티커가 인쇄된 모눈종이의 행의 개수와 열의 개수를 나타내는 Ri(1 ≤ Ri ≤ 10)와 Ci(1 ≤ Ci ≤ 10)가 한 칸의 빈칸을 사이에 두고 주어진다.
다음 Ri개의 줄에는 각 줄마다 모눈종이의 각 행을 나타내는 Ci개의 정수가 한 개의 빈칸을 사이에 두고 주어진다. 각 칸에 들어가는 값은 0, 1이다. 0은 스티커가 붙지 않은 칸을, 1은 스티커가 붙은 칸을 의미한다.
문제에서 설명한 것과 같이 스티커는 모두 올바른 모눈종이에 인쇄되어 있다. 구체적으로 스티커의 각 칸은 상하좌우로 모두 연결되어 있고, 모눈종이의 크기는 스티커의 크기에 꼭 맞아서 상하좌우에 스티커에 전혀 포함되지 않는 불필요한 행이나 열이 존재하지 않는다.
첫째 줄에 주어진 스티커들을 차례대로 붙였을 때 노트북에서 스티커가 붙은 칸의 수를 출력한다.
BaaaaaaaaaaarkingDog님이 개최하신 코딩테스트 대비 모의고사 문제 중 첫 번째 문제.
문제가 어렵진 않았으나, 좀 길다보니 긴장이 더 되기도 했다. 첫 단추가 잘못끼워진 게 일단 주어지는 스티커 데이터를 다 저장하려고 했다. 그리고 순회를 돌면서 하나씩 붙여나가면 되겠지 생각했는데, 사실 순서대로 스티커 하나씩 다 완료해나가는거라 하나씩 받고 연산을 수행하면 되던 것이였다.
붙일 수 있는가를 확인할 때도 너무 섣불리 판단해서는 안된다. 스티커의 값과 전체 맵(노트북)의 값과 같으면 붙이는게 아니다. 둘다 1(스티커가 붙여져 있음)이 아니면 붙일 수 있는 거다.
가장 헷갈리던 것은 회전이다. 좌표관련해서 회전을 시켜본 적이 없어서, 직접 적으면서 점화식을 찾았다.
내 코드
void rotate() {
for (int x = 0; x < r; ++x) {
for (int y = 0; y < c; ++y) {
tmp[y][r - 1 - x] = s[x][y];
}
}
swap(r, c);
for (int x = 0; x < r; ++x) {
for (int y = 0; y < c; ++y) {
s[x][y] = tmp[x][y];
}
}
}
다 풀고나서 보니 모범답안 코드와 조금 달랐다. 근데 내 코드가 시간이 더 소요 되는 문제가 있었다.
void rotate() {
for (int i = 0; i < r; i++)
for (int j = 0; j < c; j++)
tmp[i][j] = s[i][j];
for (int i = 0; i < c; i++)
for (int j = 0; j < r; j++)
s[i][j] = tmp[r - 1 - j][i];
swap(r, c);
}
사실 지금도 왜 이게 더 시간이 적게 걸리는 지 모르겠다. 연산과정을 따져보면 똑같지 않나? 아시는 분 있으시면 알려주십쇼 ㅠㅠ
#include <iostream>
#include <vector>
#define bb ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
int l[41][41], s[11][11], tmp[11][11]; // laptop size, sticker size
int n, m, k;
int r, c;
void rotate() {
for (int x = 0; x < r; ++x) {
for (int y = 0; y < c; ++y) {
tmp[y][r - 1 - x] = s[x][y];
}
}
swap(r, c);
for (int x = 0; x < r; ++x) {
for (int y = 0; y < c; ++y) {
s[x][y] = tmp[x][y];
}
}
}
bool glue(int& px, int& py) {
// check
for (int x = 0; x < r; ++x) {
for (int y = 0; y < c; ++y) {
if (px + x >= n || py + y >= m) return false;
if (l[px + x][py + y] && s[x][y]) return false;
}
}
// glue
for (int x = 0; x < r; ++x) {
for (int y = 0; y < c; ++y) {
if (s[x][y]) l[px + x][py + y] = 1;
}
}
return true;
}
bool solution() {
for (int rr = 0; rr < 4; ++rr) {
for (int a = 0; a < n; ++a) {
for (int b = 0; b < m; ++b) {
if (l[a][b] && s[0][0]) continue;
if (glue(a, b)) return true;
}
}
rotate();
}
return false;
}
int main() {
bb;
cin >> n >> m >> k;
int res = 0;
for (int i = 0; i < k; ++i) {
cin >> r >> c;
// sticker input
int size = 0;
for (int a = 0; a < r; ++a) {
for (int b = 0; b < c; ++b) {
cin >> s[a][b];
if (s[a][b]) ++size;
}
}
if (solution())
res += size;
}
cout << res << '\n';
return 0;
}