[백준,c++] 10703번 - 유성

문제

10703번: 유성

 

코드

#include <iostream>
using namespace std;

int N, M;

char map[3001][3001];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>N>>M;;
    for(int i=0; i<N; i++){
        string inp; cin>>inp;
        for(int k=0; k<M; k++){
            map[i][k] = inp[k];
        }
    }
    
    int move_cnt = 1e9;
    for(int i=0; i<M; i++){ // 몇 칸 이동할지 찾기
        int meteor = 0;
        int ground = 0;
        for(int k=0; k<N; k++){
            if(map[k][i] == 'X') meteor = k + 1;
            if(map[k][i] == '#'){
                ground = k + 1;
                break;
            }
        }
        if(meteor !=0 && ground != 0){
            move_cnt = min(move_cnt, ground - meteor - 1);
        }
    }
    
    for(int i=0; i<M; i++){ // 유성 이동
        for(int k=N-1; k>=0; k--){
            if(map[k][i] == 'X'){
                map[k+move_cnt][i] = 'X';
                map[k][i] = '.';
            }
        }
    }
    for(int i=0; i<N; i++){ // 출력
        for(int k=0; k<M; k++){
            cout<<map[i][k];
        }
        cout<<'\n';
    }
}

 

풀이

문제를 먼저 이해해 보자면 왼쪽 입력에서 x(유성) 뭉텅이를 땅(#) 위까지 내릴 수 있을 만큼 최대한 내려야 합니다.

따라서 가장 땅에 근접한 X(유성)을 찾아서 해당 유성과 땅과의 거리만큼 전체 유성을 내리면 됩니다.

위 입력 같은 경우 (1, 3)의 유성과 (3, 3)의 땅과의 거리차가 제일 작고, 거리 차이는 한 칸입니다. 따라서 전체 유성을 아래로 한 칸 내리면 됩니다.