728x90
반응형
목차
https://www.acmicpc.net/problem/12100
문제
문제 구현 방향 및 아이디어
생각보다 어려웠다. 아이디어는 슬라이드를 어떻게 하든 90도 돌리면 결과는 같다는 것이다.
따라서 회전하는 횟수에 따라서 슬라이드를 반복하는 재귀를 잘 구현하면 되는 문제였다.
1. 90도 회전 아이디어
아래와 같이 하면 90도 회전을 구현할 수있다.
void rotate(int board[41][41]) {
int temp[41][41] = { 0 };
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
temp[i][j] = board[N - 1 - j][i];
}
}
memcpy(board, temp, sizeof(temp));
}
2. 슬라이디 아이디어
90도 회전할 것이기 때문에 한 방향만 구현해 주면 된다.
void slide(int board[41][41]) {
int temp[41][41] = { 0 };
for (int i = 0; i < N; i++) {
int cnt = 0;
for (int j = 0; j < N; j++) {
if (board[i][j] == 0)
continue;
if (temp[i][cnt] == 0) {
temp[i][cnt] = board[i][j];
}
else if (temp[i][cnt] == board[i][j]) {
temp[i][cnt] *= 2;
cnt++;
}
else {
cnt++;
temp[i][cnt] = board[i][j];
}
}
}
memcpy(board, temp, sizeof(temp));
}
3. 재귀에 관한 아이디어
이게 생각하는게 가장 어려웠다...
원상복구가 아니기 때문에 회전한 횟수에 따라 배열을 복사해 놓고 슬라이드를 진행시킨 후 재귀를 돌리면 된다.
void game(int here, int board[41][41]) {
if (here == 5) {
counting(board);
return;
}
for (int i = 0; i < 4; i++) {
int cpy[41][41] = { 0 };
memcpy(cpy, board, sizeof(cpy));
slide(cpy);
game(here + 1, cpy);
rotate(board);
}
return;
}
코드 구현
#include<iostream>
#include<algorithm>
#include<string.h>
#include<vector>
#include<map>
#include<queue>
#include<math.h>
#include<stack>
using namespace std;
int N;
int sum = 0;
void rotate(int board[41][41]) {
int temp[41][41] = { 0 };
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
temp[i][j] = board[N - 1 - j][i];
}
}
memcpy(board, temp, sizeof(temp));
}
void slide(int board[41][41]) {
int temp[41][41] = { 0 };
for (int i = 0; i < N; i++) {
int cnt = 0;
for (int j = 0; j < N; j++) {
if (board[i][j] == 0)
continue;
if (temp[i][cnt] == 0) {
temp[i][cnt] = board[i][j];
}
else if (temp[i][cnt] == board[i][j]) {
temp[i][cnt] *= 2;
cnt++;
}
else {
cnt++;
temp[i][cnt] = board[i][j];
}
}
}
memcpy(board, temp, sizeof(temp));
}
void counting(int board[41][41]) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
sum = max(sum, board[i][j]);
}
}
}
void game(int here, int board[41][41]) {
if (here == 5) {
counting(board);
return;
}
for (int i = 0; i < 4; i++) {
int cpy[41][41] = { 0 };
memcpy(cpy, board, sizeof(cpy));
slide(cpy);
game(here + 1, cpy);
rotate(board);
}
return;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int board[41][41] = { 0 };
cin >> N;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cin >> board[i][j];
}
}
game(0, board);
cout << sum;
}
반응형
'백준 문제풀이' 카테고리의 다른 글
[백준][구현][백트래킹] 17825 주사위 윷놀이 c++구현 (0) | 2024.08.17 |
---|---|
[백준][구현] 17143 낚시왕 c++구현 (0) | 2024.08.16 |
[백준][브루트포스] 14889 스타트와 링크 c++구현 (0) | 2024.08.07 |
[백준][구현] 17144 미세먼지 안녕! c++구현 (0) | 2024.08.06 |
[백준][그리디] 1700 멀티탭 스케줄링 c++구현 (0) | 2024.08.05 |