글 읽기 - [c++] 44퍼센트 오류 해결 참고하시면 좋을 것 같습니다.

shin421179 1년 전 1

제 경우 폭발 페이즈 구현을 잘못 이해하고 구현해서 44퍼에서 wa 받았습니다.

1차원으로 쫙 펼치고 상어와 가까운 순으로 폭발시키면서 쌓았는데요, 이게 문제 상황과 결과가 다르더라구요.

블로그에 자세한 설명과 코드를 포스팅 했습니다...!

링크 :

https://velog.io/@shin421179/BOJ-21611-%EB%A7%88%EB%B2%95%EC%82%AC-%EC%83%81%EC%96%B4%EC%99%80-%EB%B8%94%EB%A6%AC%EC%9E%90%EB%93%9C

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>

using namespace std;

typedef pair<int, int> pii;

int N, M;
int board[49][49];
vector<int> flatten(2401); // 2차원 배열 -> 1차원 벡터
vector<pii> stack; // <구슬번호, 갯수>
vector<int> arranged(2401); // 폭발 후 그룹핑 벡터
int bombCnt[4] = {0, 0, 0, 0}; // 0번째 더미 + 각 구슬의 폭발횟수 카운트
int dy[5] = {-1, 1, 0, 0};
int dx[5] = {0, 0, -1, 1}; // 상하좌우

void input(){
    cin >> N >> M;
    for (int i = 0; i < N; i++){
        for (int j = 0; j < N;j++){
            cin >> board[i][j];
        }
    }
}

int flat(int y,int x){
    int r = N / 2;
    int dist = max(abs(y - r), abs(x - r));

    if (dist == 0)
        return 0;

    int ifL = (y > r - dist) && (x == r - dist);
    int ifD = !ifL && (y == r + dist);
    int ifR = !ifD && (x == r + dist);
    int ifU = !ifR && (y == r - dist);
    int dir = ifL + ifD * 2 + ifR * 3 + ifU * 4 - 1; // 좌하우상
    int idx = (2 * dist - 1) * (2 * dist - 1) + 2 * dir * dist;
    idx += ifL * (dist - r + y - 1) + ifD * (dist - r + x - 1) + ifR * (r + dist - y - 1) + ifU * (r + dist - x - 1);

    return idx;
}

void flat2D(){
    for (int i = 0; i < N; i++){
        for (int j = 0; j < N;j++){
            flatten[flat(i, j)] = board[i][j];
        }
    }
}

void blizzard(int dir, int dist){
    int cef, sign, idx;
    cef = dir & 1 ? 3 : 1;
    sign = dir & 2 ? -1 : 1;

    while (dist>0){
        idx = 4 * dist * dist + sign * cef * dist;
        flatten[idx] = 0;
        dist--;
    }
}

void initStack(){
    for (int i = 0; i < N * N; i++){
        int next = flatten[i];
        if (next == 0)
            continue;
        
        if (stack.empty() || stack.back().first!=next){
            stack.push_back({next, 1});
            continue;
        } else if (stack.back().first == next){
            stack.back().second++;
        }
    }
}

void explodeStack(){
    vector<pii>::iterator it = stack.begin();
    while (!stack.empty() && it != stack.end()){
        pii elem = *it;
        if (elem.second < 4){
            it++;
            continue;
        }
        bombCnt[elem.first] += elem.second;
        it = stack.erase(it);
    }
}

bool updateStack(){
    vector<pii>::iterator it = stack.begin() + 1;
    bool isChanged = false;

    while(!stack.empty() && it != stack.end()){
        if ((*(it - 1)).first == (*it).first){
            (*(it - 1)).second += (*it).second;
            it = stack.erase(it);
            isChanged = true;
        }else{
            it++;
        }
    }
    return isChanged;
}

void explode(){
    bool isChanged = true;
    initStack();

    while (isChanged){
        explodeStack();
        isChanged = updateStack();
    }
}

void rearrange(){
    int idx = 1;

    reverse(stack.begin(), stack.end());

    while(!stack.empty()){
        if (idx >= N * N){
            stack.clear();
            break;
        }

        flatten[idx++] = stack.back().second;
        flatten[idx++] = stack.back().first;
        stack.pop_back();
    }

    while(idx<N*N){
        flatten[idx++] = 0;
    }
}

void solution(){
    int dir, dist, ans = 0;
    input();
    flat2D();
    while (M--){
        cin >> dir >> dist;
        blizzard(dir, dist);
        explode();
        rearrange();
    }
    ans = bombCnt[1] + bombCnt[2] * 2 + bombCnt[3] * 3;
    cout << ans << '\n';
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL); cout.tie(NULL);

    solution();
}

coding_data_pul 1년 전 0

블로그 링크는 달아도 되는대,

유튜브 링크는 달면, 운영자님이 다 지운 걸까요?

coding_data_pul 1년 전 0

4개이상 같은 종류의 구슬이 모이면, 모두 동시에 폭발해야 합니다.

문제 설명에서, 2번 구슬 4개와, 3번 구슬 5개가 동시에 폭발하고 있습니다.

shin421179 1년 전 0

@coding_data_pul

그 부분을 설명하기 위한 글입니다!! 제 벨로그 글 읽어보시면 자세히 설명해놓았습니다 :)

ghkoh_97 1년 전 3

블로그 링크가 이상해서 찾는데 한참 걸렸네요

@shin421179 님 블로그에 적혀있는 반례 가져옵니다

9 1
0 0 0 0 0 0 0 0 0
3 2 1 3 1 3 3 3 0
1 3 3 3 1 3 3 1 0
0 2 2 2 1 2 2 1 0
0 1 2 1 0 2 2 1 0
0 3 3 1 1 2 2 2 0
0 3 3 3 1 1 1 2 0
0 1 1 1 3 3 3 2 0
0 0 0 0 0 0 0 0 0
1 3

answer: 97

explanation
111222()22233311122233()3332133111333222111333()31231 0
11122222233311122233333213311133322211133331231 0
111()33311122233333213311133322211133331231 12
111()333111222()213311133322211133331231 27
111()333111222()2133111333222111()1231 39
11133311122221331113332221111231 39
111333111()1331113332221111231 47
111333111()133111333222()231 51
111333111133111333222231 51
111333()33111333222231 55
111333()33111333()31 63
1113333311133331 63
111()11133331 78
111()111()1 90
1111111 90
() 97

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[c++] 44퍼센트 오류 해결 참고하시면 좋을 것 같습니다.

shin421179 1년 전 1

coding_data_pul 1년 전 0

coding_data_pul 1년 전 0

shin421179 1년 전 0

ghkoh_97 1년 전 3

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말