15683 | 감시
#include <bits/stdc++.h>
using namespace std;
int N, M, cc_num, watched, wall;
int board[8][8], tmp[8][8], dir[8];
tuple<int, int, int> cctv[8];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, -1, 0, 1};
int watch(int x, int y, int d) {
int cnt = 0;
while (1) {
x += dx[d];
y += dy[d];
if (x < 0 || x >= N || y < 0 || y >= M) break;
if (tmp[x][y] == 6) break;
if (tmp[x][y] == 0) {
tmp[x][y] = -1;
++cnt;
}
}
return cnt;
}
void simulation() {
for (int i = 0; i < N; ++i) {
for (int j = 0; j < M; ++j) tmp[i][j] = board[i][j];
}
int cnt = 0;
for (int i = 0; i < cc_num; ++i) {
auto [x, y, n] = cctv[i];
switch (n) {
case 1:
cnt += watch(x, y, dir[i]);
break;
case 2:
cnt += watch(x, y, dir[i]);
cnt += watch(x, y, dir[i] + 2);
break;
case 3:
cnt += watch(x, y, dir[i]);
cnt += watch(x, y, (dir[i] + 1) % 4);
break;
case 4:
cnt += watch(x, y, dir[i]);
cnt += watch(x, y, (dir[i] + 1) % 4);
cnt += watch(x, y, (dir[i] + 2) % 4);
break;
case 5:
cnt += watch(x, y, 0);
cnt += watch(x, y, 1);
cnt += watch(x, y, 2);
cnt += watch(x, y, 3);
break;
}
}
watched = max(watched, cnt);
}
void dfs(int k) {
if (k == cc_num) {
simulation();
return;
}
auto [x, y, n] = cctv[k];
if (n == 5) {
dir[k] = 0;
dfs(k + 1);
} else if (n == 2) {
for (int i = 0; i < 2; ++i) {
dir[k] = i;
dfs(k + 1);
}
} else {
for (int i = 0; i < 4; ++i) {
dir[k] = i;
dfs(k + 1);
}
}
}
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N >> M;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < M; ++j) {
cin >> board[i][j];
if (board[i][j] >= 1 && board[i][j] <= 5)
cctv[cc_num++] = {i, j, board[i][j]};
if (board[i][j] == 6) ++wall;
}
}
dfs(0);
cout << N * M - wall - cc_num - watched;
}에효효 뭔가 시뮬레이션은 비교적 구현이 복잡해지니까 한번 삐끗하면 어디가 잘못됐는지 찾을 수가 없다...
인덱스 사용에 항상 주의하기
정신 바짝 차리고 풀기.. 그래도 이제 dfs는 마스터한 것 같다
18808 | 스티커 붙이기
ver 1
#include <bits/stdc++.h>
using namespace std;
int board[40][40], tmp[40][40];
int sticker[100][4][10][10];
int N, M, K, R, C;
bool is_ok(int x, int y, int k, int d) {
// board x,y에 스티커 붙일 수 있는가
for (int i = 0; i < N; ++i) {
for (int j = 0; j < M; ++j) tmp[i][j] = board[i][j];
}
for (int i = 0; i < R; ++i) {
for (int j = 0; j < C; ++j) {
if (x + i >= N || y + j >= M) return false;
if (sticker[k][d][i][j] && tmp[x + i][y + j]) return false;
if (sticker[k][d][i][j]) tmp[x + i][y + j] = sticker[k][d][i][j];
}
}
return true;
}
void rotate(int k, int d) {
swap(R, C);
for (int i = 0; i < R; ++i) {
for (int j = 0; j < C; ++j) {
sticker[k][d][i][j] = sticker[k][d - 1][C - j - 1][i];
}
}
}
void simulation(int k) {
for (int d = 0; d < 4; ++d) {
if (d > 0) rotate(k, d);
for (int x = 0; x < N; ++x) {
for (int y = 0; y < M; ++y) {
if (is_ok(x, y, k, d)) {
swap(board, tmp);
return;
}
}
}
}
}
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N >> M >> K;
for (int k = 0; k < K; ++k) {
cin >> R >> C;
for (int i = 0; i < R; ++i) {
for (int j = 0; j < C; ++j) cin >> sticker[k][0][i][j];
}
simulation(k);
}
int cnt = 0;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < M; ++j)
if (board[i][j]) ++cnt;
}
cout << cnt;
}처음엔 스티커를 전부 다 입력 받고 시뮬레이션을 돌려줬었다.
그래서 배열도 크기가 굉장히 컸었다.
그런데 불필요했다. 그냥 각 시점마다 스티커를 붙일 수 있는지 없는지 판단한 다음 최초로 붙일 수 있는 자리에 붙이면 되는 거였다.
그리고 스티커를 붙일 수 있는지 없는지 판단할 때 board값을 업데이트 해가는 게 아니라, 붙일 수 있는지 판단이 끝나고 나면 board 값을 한번에 업데이트 하는 것이 불필요한 복사 비용을 줄이는 것이었다.
개선 버전
#include <bits/stdc++.h>
using namespace std;
int board[40][40];
int sticker[10][10];
int N, M, K, R, C;
bool put(int x, int y) {
for (int i = 0; i < R; ++i) {
for (int j = 0; j < C; ++j) {
if (x + i >= N || y + j >= M) return false;
if (sticker[i][j] && board[x + i][y + j]) return false;
}
}
for (int i = 0; i < R; ++i) {
for (int j = 0; j < C; ++j) {
if (sticker[i][j]) board[x + i][y + j] = 1;
}
}
return true;
}
void rotate() {
int tmp[10][10] = {};
for (int i = 0; i < R; ++i) {
for (int j = 0; j < C; ++j) {
tmp[j][R - 1 - i] = sticker[i][j];
}
}
swap(R, C);
for (int i = 0; i < R; ++i) {
for (int j = 0; j < C; ++j) {
sticker[i][j] = tmp[i][j];
}
}
}
void simulation() {
for (int d = 0; d < 4; ++d) {
if (d > 0) rotate();
for (int x = 0; x < N; ++x) {
for (int y = 0; y < M; ++y) {
if (put(x, y)) return;
}
}
}
}
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N >> M >> K;
for (int k = 0; k < K; ++k) {
cin >> R >> C;
for (int i = 0; i < R; ++i) {
for (int j = 0; j < C; ++j) cin >> sticker[i][j];
}
simulation();
}
int cnt = 0;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < M; ++j)
if (board[i][j]) ++cnt;
}
cout << cnt;
}인덱스 사용 주의!
12100 | 2048 (Easy)
ver1
#include <bits/stdc++.h>
using namespace std;
#define BLOCK first
#define MIXED second
int N, ans;
pair<int, bool> board[20][20];
void rotate() {
pair<int, bool> tmp[20][20] = {};
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
tmp[j][N - 1 - i] = board[i][j];
}
}
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
board[i][j] = tmp[i][j];
}
}
}
bool move(int x, int y, int i, int j) {
if (board[x][y].BLOCK == 0) {
if (y == 0) {
board[x][y] = board[i][j];
board[i][j] = {0, 0};
return true;
}
return false;
}
if (!board[x][y].MIXED && board[x][y].BLOCK == board[i][j].BLOCK) {
board[x][y].BLOCK *= 2;
board[x][y].MIXED = 1;
board[i][j] = {0, 0};
return true;
}
if (y + 1 == j) return true;
board[x][y + 1] = board[i][j];
board[i][j] = {0, 0};
return true;
}
void slide() {
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) board[i][j].MIXED = 0;
}
for (int i = 0; i < N; ++i) {
for (int j = 1; j < N; ++j) {
for (int goal = j - 1; goal >= 0; --goal) {
if (move(i, goal, i, j)) break;
}
}
}
}
void dfs(int k) {
if (k == 5) {
for (int i = 0; i < N; ++i)
for (int j = 0; j < N; ++j) ans = max(ans, board[i][j].BLOCK);
return;
}
pair<int, bool> backup[20][20];
for (int r = 0; r < 4; ++r) {
memcpy(backup, board, sizeof board); // 상태 저장
for (int i = 0; i < r; ++i) rotate();
slide();
dfs(k + 1);
memcpy(board, backup, sizeof board); // 상태 복구
}
}
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
cin >> board[i][j].BLOCK;
}
}
dfs(0);
cout << ans;
}ver2
#include <bits/stdc++.h>
using namespace std;
int N, ans, dir[5];
int board[20][20], board2[20][20];
void rotate() {
int tmp[20][20] = {};
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
tmp[j][N - 1 - i] = board2[i][j];
}
}
memcpy(board2, tmp, sizeof tmp);
}
void swipe() {
for (int i = 0; i < N; ++i) {
int idx = 0;
int tmp[20] = {};
for (int j = 0; j < N; ++j) {
if (!board2[i][j]) continue;
if (!tmp[idx])
tmp[idx] = board2[i][j];
else if (tmp[idx] == board2[i][j])
tmp[idx++] *= 2;
else
tmp[++idx] = board2[i][j];
}
memcpy(board2[i], tmp, sizeof tmp);
}
}
void dfs(int k) {
if (k == 5) {
memcpy(board2, board, sizeof board);
for (int i = 0; i < 5; ++i) {
for (int r = 0; r < dir[i]; ++r) rotate();
swipe();
}
for (int i = 0; i < N; ++i)
for (int j = 0; j < N; ++j) ans = max(ans, board2[i][j]);
return;
}
for (int r = 0; r < 4; ++r) {
dir[k] = r;
dfs(k + 1);
}
}
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) cin >> board[i][j];
}
dfs(0);
cout << ans;
}ver1에서는 board 배열 자체에서 블록을 이동시키면서 상태를 바로 업데이트했었다.
그런데 이렇게 하다 보니 MIXED 같은 상태값을 따로 관리해야 했고,
이 때문에 로직이 복잡해질 수밖에 없었다.
그런데 바킹독님의 풀이를 보니, 한 줄 단위로 tmp 배열을 만들어서
슬라이드 결과만 따로 저장해두고, 그걸 마지막에 한 번에 복사하고 있었다.
그럼 굳이 MIXED 여부를 따질 필요가 없다.
앞으로 값 복사는 memcpy 활용 잘해보자. 시간이 훨씬 줄어든다.
15686 | 치킨 배달
#include <bits/stdc++.h>
using namespace std;
pair<int, int> chicken[13];
int chosen[13], board[50][50];
int N, M, c_num, ans = INT_MAX;
int dist(int i, int j) {
int d = INT_MAX;
for (int k = 0; k < M; ++k) {
auto [x, y] = chicken[chosen[k]];
d = min(d, abs(x - i) + abs(y - j));
}
return d;
}
void dfs(int k, int st) {
if (k == M) {
int d = 0;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
if (board[i][j] == 1) d += dist(i, j);
}
}
ans = min(ans, d);
return;
}
for (int i = st; i < c_num; ++i) {
chosen[k] = i;
dfs(k + 1, i + 1);
}
}
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N >> M;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
cin >> board[i][j];
if (board[i][j] == 2) chicken[c_num++] = {i, j};
}
}
dfs(0, 0);
cout << ans;
}쉽다. 근데 처음에 최단 거리인 거 보고 bfs를 떠올렸는데 이 문제는 그렇게 할 필요가 없었다.
그냥 조합을 구해주고 치킨집 좌표 - 집 좌표만 해주면 된다.
11559 | Puyo Puyo
#include <bits/stdc++.h>
using namespace std;
char board[12][6];
queue<pair<int, int> > q;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, -1, 0, 1};
int ans;
void fall() {
for (int i = 10; i >= 0; --i) {
for (int j = 0; j < 6; ++j) {
if (board[i][j] != '.') {
int f = i;
while (1) {
if (f == 11) break;
if (board[f + 1][j] != '.') break;
++f;
}
swap(board[i][j], board[f][j]);
}
}
}
}
bool bfs(int i, int j) {
bool visit[12][6] = {};
int area = 0;
q.push({i, j});
visit[i][j] = 1;
++area;
while (!q.empty()) {
auto [x, y] = q.front();
q.pop();
for (int d = 0; d < 4; ++d) {
int nx = x + dx[d], ny = y + dy[d];
if (nx < 0 || nx >= 12 || ny < 0 || ny >= 6) continue;
if (visit[nx][ny] || board[nx][ny] != board[i][j]) continue;
q.push({nx, ny});
visit[nx][ny] = 1;
++area;
}
}
if (area >= 4) {
for (int i = 0; i < 12; ++i) {
for (int j = 0; j < 6; ++j) {
if (visit[i][j]) board[i][j] = '.';
}
}
return true;
}
return false;
}
bool bomb() {
bool flag = 0;
for (int i = 0; i < 12; ++i) {
for (int j = 0; j < 6; ++j) {
if (board[i][j] != '.') {
if (bfs(i, j)) flag = 1;
}
}
}
return flag;
}
void run() {
while (1) {
if (!bomb()) return;
fall();
++ans;
}
}
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
for (int i = 0; i < 12; ++i) {
for (int j = 0; j < 6; ++j) cin >> board[i][j];
}
run();
cout << ans;
}이번 풀이 좀 맘에 든다!! 아이디어 빠르게 내고 바로 맞았다
근데 fall 함수 for문 사용이 처음에 잘못 됐었다.
중력 방향으로 작용하니까 for(int i = 0; i < 12; ++i)로 할 게 아니라
for (int i = 10; i >= 0; --i) 로 해서 아래서부터 떨어뜨려 줬어야 했음.
다행히 출력해보고 이상한 점 바로 찾아냈다.
print 함수들을 만들어놓고 중간 중간 과정 출력해보면서 진행하기! 그래야 파악이 쉽다.
14891 | 톱니바퀴
ver1
#include <bits/stdc++.h>
using namespace std;
int circle[4][8];
void rotate(int idx, int dir) {
if (dir == 1) {
int tmp = circle[idx][7];
for (int i = 7; i > 0; --i) circle[idx][i] = circle[idx][i - 1];
circle[idx][0] = tmp;
} else {
int tmp = circle[idx][0];
for (int i = 0; i < 7; ++i) circle[idx][i] = circle[idx][i + 1];
circle[idx][7] = tmp;
}
}
void run() {
int idx, r[4] = {};
cin >> idx >> r[--idx];
// left
for (int i = idx; i > 0; --i) {
if (circle[i][6] == circle[i - 1][2]) break;
r[i - 1] = r[i] * -1;
}
// right
for (int i = idx; i < 3; ++i) {
if (circle[i][2] == circle[i + 1][6]) break;
r[i + 1] = r[i] * -1;
}
for (int i = 0; i < 4; ++i) {
if (r[i]) rotate(i, r[i]);
}
}
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
for (int i = 0; i < 4; ++i) {
for (int j = 0; j < 8; ++j) {
char c;
cin >> c;
circle[i][j] = c - '0';
}
}
int k;
cin >> k;
while (k--) run();
int ans = 0;
for (int i = 0; i < 4; ++i) ans += circle[i][0] * (1 << i);
cout << ans;
}에혀.. 로직은 빨리 생각해냈는데 답이 틀리길래 한참 헤맸다 이유는 인덱스....
여기서 톱니바퀴를 1번부터 1,2,3,4로 세고 있어서
--idx로 받아야 하는데 그냥 받아버렸었다..
cin >> idx >> r[idx]; => cin >> idx >> r[--idx];
고치고 성공...
바킹독님 풀이 보니까 STL에 이미 rotate 함수가 있었다;;
rotate(begin, middle, end);[begin, middle) 구간을 뒤로 보내고
[middle, end) 구간을 앞으로 가져오는 회전을 함.
그래서 오른쪽으로 회전은
rotate(v.begin(), v.begin() + v.size() - 1, v.end());왼쪽 회전은
rotate(v.begin(), v.begin() + 1, v.end());stl rotate 사용
#include <bits/stdc++.h>
using namespace std;
int circle[4][8];
void run() {
int idx, r[4] = {};
cin >> idx >> r[--idx];
// left
for (int i = idx; i > 0; --i) {
if (circle[i][6] == circle[i - 1][2]) break;
r[i - 1] = r[i] * -1;
}
// right
for (int i = idx; i < 3; ++i) {
if (circle[i][2] == circle[i + 1][6]) break;
r[i + 1] = r[i] * -1;
}
for (int i = 0; i < 4; ++i) {
if (r[i] == 0) continue;
if (r[i] == 1)
rotate(circle[i], circle[i] + 7, circle[i] + 8);
else
rotate(circle[i], circle[i] + 1, circle[i] + 8);
}
}
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
for (int i = 0; i < 4; ++i) {
for (int j = 0; j < 8; ++j) {
char c;
cin >> c;
circle[i][j] = c - '0';
}
}
int k;
cin >> k;
while (k--) run();
int ans = 0;
for (int i = 0; i < 4; ++i) ans += circle[i][0] * (1 << i);
cout << ans;
}STL 사용하면 훨 깔끔!
14499 | 주사위 굴리기
#include <bits/stdc++.h>
using namespace std;
int board[20][20];
int N, M, x, y, K;
int dx[5] = {0, 0, 0, -1, 1};
int dy[5] = {0, 1, -1, 0, 0};
int dice[6];
/*
1
3 0 2
4
5
*/
void roll(int d) {
int tmp[6];
memcpy(tmp, dice, sizeof dice);
if (d == 1) {
dice[0] = tmp[2];
dice[2] = tmp[5];
dice[3] = tmp[0];
dice[5] = tmp[3];
} else if (d == 2) {
dice[0] = tmp[3];
dice[2] = tmp[0];
dice[3] = tmp[5];
dice[5] = tmp[2];
} else if (d == 3) {
dice[0] = tmp[1];
dice[1] = tmp[5];
dice[4] = tmp[0];
dice[5] = tmp[4];
} else if (d == 4) {
dice[0] = tmp[4];
dice[1] = tmp[0];
dice[4] = tmp[5];
dice[5] = tmp[1];
}
}
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N >> M >> x >> y >> K;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < M; ++j) cin >> board[i][j];
}
while (K--) {
int d;
cin >> d;
int nx = x + dx[d], ny = y + dy[d];
if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
roll(d);
if (board[nx][ny] == 0)
board[nx][ny] = dice[0];
else {
dice[0] = board[nx][ny];
board[nx][ny] = 0;
}
cout << dice[5] << '\n';
x = nx, y = ny;
}roll이 중요한 거였다.
각 면을 인덱스로 매핑하고 굴리는 규칙만 확실히 정리하면 간단한 문제다.
근데 너무 헷갈리는 게 문제..
주사위 면을 배열로 표현하기
6면의 주사위를 1차원 배열 dice[6]로 표현한다.
이때, 각 인덱스를 주사위의 면에 원하는 대로 대응시킨다:
처음 문제를 풀 때 윗면이 1이라고 놓았다는 조건을 만족하게끔 주사위 인덱스를 설정해줘야 하는 줄 알았다.
"문제에서 윗면이 1번이라고 했는데, 꼭dice[1]을 윗면으로 써야 하나요?"
정답은 그럴 필요 없다!
주사위의 각 면을 배열로 표현할 때, 인덱스 번호는 전적으로 구현자의 선택이다.
중요한 건 각 인덱스가 어떤 면을 의미하는지 명확하게 정하고, 그 기준을 일관되게 유지하는 것이다.🧱 예시 구조: 윗면이 2번인 주사위
// [3] // [6][2][5] // [1] // [4] 즉, 윗면이 dice[2], 바닥면이 dice[4]인 구조로 설정한 것이다. 그리고 문제에서 "윗면의 숫자를 출력하라"고 했다면, 그에 맞게 cout << dice[2]; 를 해주면 된다.
1
3 0 2
4
5일 때
→ 으로 굴리면
Before: After:
1 1
3 0 2 → 0 2 5
4 4
5 3
← 으로 굴리면
Before: After:
1 1
3 0 2 → 5 3 0
4 4
5 2↑으로 굴리면
Before: After:
1 5
3 0 2 ↑ 3 1 2
4 0
5 4↓으로 굴리면
Before: After:
1 0
3 0 2 ↓ 3 4 2
4 5
5 1잘 보면 좌우(←, →) 회전에서는 바닥면을 기준으로 상하 위치의 면이 당겨진다.
또 상하(↑, ↓) 회전에서는 바닥면을 기준으로 앞뒤 위치의 면이 당겨진다.
또한 주사위는 항상 (3, 2), (1, 4), (0, 5) 면이 서로 마주 본다.
이 점을 기준으로 내가 예상한 주사위 인덱스의 변화가 정확한지 점검하면 쉽다.
