수학과의 좌충우돌 프로그래밍

[C++] BAEKJOON 9455번 박스(ACM-ICPC Daejeon 2013) 본문

알고리즘/C++

[C++] BAEKJOON 9455번 박스(ACM-ICPC Daejeon 2013)

ssung.k 2019. 7. 26. 02:57

문제 보러 가기

 

9455번: 박스

문제 m행 n열로 이루어진 그리드가 주어진다. 일부 칸에는 박스가 들어 있다. 모든 박스가 더 이상 움직일 수 없을 때 까지 아래로 움직인다면, 박스는 쌓여진 상태가 된다. 그림 (a)의 그리드의 크기는 5행 4열이고, 7칸에는 박스가 들어있다. 모든 박스가 계속해서 아래로 움직이면, 그림 (b)와 같이 변하게 된다. 박스가 움직인 거리는 바닥에 쌓이기 전 까지 이동한 칸의 개수이다. 예를 들어, 맨 왼쪽 열에서 가장 위에 있는 박스가 움직인 거리는 2이

www.acmicpc.net

 

ACM-ICPC 문제라고 하기에 쉽고 간단한 문제 였습니다.

박스는 각 column 에서만 이동을 할 수 있으므로 column 을 기준으로 나눠서 생각해주었습니다. 박스가 있을 경우, 바닥으로 부터 거리를 구해주는데 dump 라는 변수를 만들어서 현재 바닥으로 부터 몇 개의 박스가 쌓여 있나를 확인해주었습니다. 바닥으로 부터의 거리 - 쌓여있는 박스의 개수 를 통해 해당 박스가 움직인 거리를 구할 수 있습니다. 이를 모두 더해주어서 모든 박스의 총 이동거리를 구했습니다.

#include <iostream>

using namespace std;

int grid[100][100];

int main(int argc, const char * argv[]) {
    
    int T;
    cin >> T;
    
    for (int t=0;t<T;t++){
        
        int M,N;
        cin >> M >> N;
        
        for (int i=0;i<M;i++){
            for (int j=0;j<N;j++){
                cin >> grid[i][j];
            }
        }
        // 총 이동거리
        int totalDis = 0;
        for (int col=0;col<N;col++){
            // 해당 column 에서 바닥에 쌓인 갯수
            int dump = 0;
            for (int row=M-1;row>=0;row--){
                if (grid[row][col] == 1){
                    totalDis += (M-1)-row-dump;
                    dump++;
                }
            }
        }
        cout << totalDis << endl;
    }
    return 0;
}

 

 

Comments