https://www.acmicpc.net/problem/21611
21611번: 마법사 상어와 블리자드
마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그, 비바라기 마법을 할 수 있다. 오늘 새로 배운 마법은 블리자드이고, 크기가 N×N인 격자에서 연습하려고 한다. N은 항상 홀수이고, (
www.acmicpc.net
소요 시간
골드 2 기준으로 2시간이 소요되었습니다 ㅠㅠ
확실히 골드 1 치고는 어렵긴 했지만 이렇게 오래 걸려서야... 걱정이 크네요...
구상
보자마자 아... 너무 귀찮아서... 배열을 동글동글 회오리 모양으로 접근해야 하기 때문에, 차라리 이 회오리를 펼쳐서 칸 번호 순서로 나열된 1차원 배열로 표현하자는 생각이 들었습니다. 이렇게 해도 되고, 1차원 2차원 배열 둘 다 사용하면서 서로의 좌표를 map으로 대응시켜 찾아봐도 됩니다. 저는 1차원 배열만 사용했을 때 파괴된 구슬의 빈 칸을 채우는 구현이 더 간단해 질 것 같았고, 굳이 2차원 배열이 필요한 이유를 찾을 수 없어서 1차원 배열만 사용했습니다. 어떤 방법을 택하시든 칸 번호로 접근하기 편해야 합니다.
[1차원 배열만 사용할 때 편한 점]
- 빈 칸을 채우는 구현이 편하다(vector erase, remove함수로 간편하게 구현 가능)
- 연속하는 구슬을 확인하기 편하다
[1차원 배열만 사용할 때 불편한 점]
- d방향으로 s내의 칸을 찾기 불편하다. (마법이 시전되는 칸을 찾기 불편하다.)
아마도 2차원 1차원 둘 다 사용하신 분들은 2차원이 없으면 마법이 시전되는 칸을 찾기 어렵다고 생각하신 것 같습니다. 저도 이 부분 때문에 구상 시간을 좀 썼고, 결론적으로 마법이 시전되는 칸 번호의 규칙성을 찾아서 1차원 배열만 사용하면서 마법이 시전되는 칸의 칸번호를 찾을 수 있었습니다.
칸 번호 규칙성(중요)
왼쪽 : 1, 10, 27, 52
아래 : 3, 14, 33, 60
오른쪽 : 5, 18, 39, 68
위쪽 : 7, 22, 45, 76
보이시나요?! 증가량만 적어 보면
왼쪽 : 1, 9, 17, 25
아래 : 3, 11, 19, 27
오른쪽 : 5, 13, 21, 29
위쪽 : 7, 15, 23, 31
즉, 증가량이 8씩 증가하는 계차수열입니다.(아~ 계차수열이라는 말이 너무 오랜만이네용 ㅎㅎㅎ)
이런 일이 일어나는 이유는 당연하게도, 마법이 시전되는 다음 칸을 찾기 위해서는 한바퀴에 해당하는 칸의 갯수를 더해줘야 하는데, 회오리의 바깥쪽으로 갈수록 한 바퀴라는 것이 8씩 증가하기 때문입니다.
아무튼 초기값만 방향에 따라 1, 3, 5, 7로 설정해 주고(변환배열 사용하면 편합니다!) s개의 계차수열 항을 찾아주면 그 항들이 바로 마법이 시전되는 칸의 번호입니다.
위 규칙성을 반영하여 마법 시전부를 구현하고 나면, 사실 구슬을 폭파하는 것이나 변화시키는 것은 쉽습니다.
*** 주의사항 : 구현 시에 0을 맨 뒤 빈칸으로 생각하시고, 0을 0번 구슬로 카운트하지 않도록 조심하셔야 합니당
코드
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
int diToNum[5] = {0, 7, 3, 1, 5};
int answer = 0;
void do_magic(vector<int>& board, int N, int si, int di) {
int prev = 0; int now = diToNum[di];
for(int j=0; j<si; j++) {
board[now] = -1;
int tmp = prev;
prev = now; now = now + (now-tmp) + 8;
}
board.erase(remove(board.begin(), board.end(), -1), board.end()); //정리
while(board.size() != N*N) {
board.push_back(0);
}
}
void explode(vector<int>& board, int N) {
bool exploded = true;
while(exploded) {
exploded = false;
int prev = 0; int combo;
for(int i=1; i<N*N; i++) {
int now = board[i];
if(now == 0) break;
if(now == prev) {
combo += 1;
if(combo == 4) {
board[i] = -1; board[i-1] = -1; board[i-2] = -1; board[i-3] = -1;
exploded = true;
answer += now*combo;
}
else if(combo > 4) {
board[i] = -1;
answer += now;
}
}
else {
combo = 1;
}
prev = now;
}
board.erase(remove(board.begin(), board.end(), -1), board.end()); //정리
while(board.size() != N*N) {
board.push_back(0);
}
}
}
void change(vector<int>& board, int N) {
vector<int> new_board;
new_board.push_back(0);
int prev = board[1]; int combo = 1;
if(prev != 0) {
for(int i=2; i<N*N; i++) {
if(board[i] == 0 || new_board.size() > N*N) break;
if(prev == board[i]) {
combo += 1;
}
else {
//grouped
new_board.push_back(combo); new_board.push_back(prev);
combo = 1;
}
prev = board[i];
}
new_board.push_back(combo); new_board.push_back(prev);
}
while(new_board.size() > N*N) {
new_board.pop_back();
}
while(new_board.size() < N*N) {
new_board.push_back(0);
}
board = new_board;
}
int main(int argc, char** argv)
{
ios_base :: sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int N, M; answer = 0;
cin >> N >> M;
vector<vector<int> > twoD(N, vector<int>(N, 0));
for(int i=0; i<N; i++) {
for(int j=0; j<N; j++) {
cin >> twoD[i][j];
}
}
vector<int> board;
board.push_back(twoD[N/2][N/2]);
// 2, 2, 2, 2, 4, 4, 4, 4, 6, 6, 6, 6, n은 홀수이므로 n-1까지
int start_x = N/2; int start_y = N/2-1;
for(int i=2; i<N; i+=2) {
//down
for(int j=0; j<i; j++) {
board.push_back(twoD[start_x][start_y]);
start_x += 1;
}
start_x -= 1; start_y += 1;
//right
for(int j=0; j<i; j++) {
board.push_back(twoD[start_x][start_y]);
start_y += 1;
}
start_x -= 1; start_y -= 1;
//up
for(int j=0; j<i; j++) {
board.push_back(twoD[start_x][start_y]);
start_x -= 1;
}
start_x += 1; start_y -= 1;
//left
for(int j=0; j<i; j++) {
board.push_back(twoD[start_x][start_y]);
start_y -= 1;
}
}
for(int i=0; i<M; i++) {
int si, di;
cin >> di >> si;
do_magic(board, N, si, di);
explode(board, N);
change(board, N);
}
cout << answer << endl;
return 0;
}
'PS문제들' 카테고리의 다른 글
[백준] 21610번 : 마법사 상어와 비바라기 (C++) (0) | 2022.10.13 |
---|---|
[백준] 23291번: 어항 정리 (0) | 2022.10.12 |
[백준] 23290번: 마법사 상어와 복제 (0) | 2022.10.12 |
[해커랭크] PS(Intermediate) Certification 후기 (0) | 2022.10.04 |
[백준] 23289: 온풍기 안녕!(C++, 하드코딩 적은 풀이) (0) | 2022.10.01 |
댓글