문제출처: https://www.acmicpc.net/problem/9455
문제
m행 n열로 이루어진 그리드가 주어진다. 일부 칸에는 박스가 들어 있다. 모든 박스가 더 이상 움직일 수 없을 때 까지 아래로 움직인다면, 박스는 쌓여진 상태가 된다.
그림 (a)의 그리드의 크기는 5행 4열이고, 7칸에는 박스가 들어있다. 모든 박스가 계속해서 아래로 움직이면, 그림 (b)와 같이 변하게 된다.
박스가 움직인 거리는 바닥에 쌓이기 전 까지 이동한 칸의 개수이다. 예를 들어, 맨 왼쪽 열에서 가장 위에 있는 박스가 움직인 거리는 2이다. 모든 박스가 이동한 거리 (각 박스가 이동한 거리의 합) 을 구하는 프로그램을 작성하시오. 위의 예제에서 박스 7개가 움직인 거리는 8이다.
입력
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 m과 n이 주어진다. (1 ≤ m, n ≤ 100) 다음 m개 줄에는 그리드의 각 행의 정보를 나타내는 n개의 정수가 주어진다. 그리드 첫 행부터 마지막 행까지 순서대로 주어진다. 박스가 들어있는 칸은 1로, 다른 칸은 0으로 주어진다. 각 정수 사이에는 공백이 하나 주어진다.
출력
각 테스트 케이스마다 입력으로 주어진 그리드에서 모든 박스가 이동한 거리를 출력한다.
풀이
삼성sw exprt 문제에서 본 것 같은데 단순히 문제를 코드로 구현할 수 있는지를 보는 문제입니다.
각 열 마다 박스가 움직이는 횟수를 알아야하고(box변수), 모든 열을 조사하여 박스의 총 이동횟수를 구해야합니다(ans변수). 방법1(30행~36행)은 박스가 땅에 떨어질때 횟수를 세므로, 마지막인덱스-현재위치-박스움직임의횟수 로 구할 수 있습니다. 방법2는 방법1을 개선한 코드로, 더 직관적이라고 할 수 있습니다.
코드
#include<iostream> #include<algorithm> int map[100][100]; using namespace std; int main() { int t,m,n; cin.tie(0); cin.sync_with_stdio(false); cin >> t; for (int i = 0; i < t; i++) { //답을 출력하기위한 ans변수 int ans = 0; cin >> m >> n; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { cin >> map[i][j]; } } for (int i = 0; i < n; i++) { //각 열 마다 박스이동횟수 초기화 int box = 0; for (int j = m - 1; j >= 0; j--) { //방법1 //현재자리가 박스 놓여져있을 때 if (map[j][i] == 1) { //마지막행인덱스-현재위치-움직인박스길이 ans += (m - 1) - j - box; //박스 한칸움직임. box++; } //방법2 /*if (map[j][i] == 0) box++; else ans += box;*/ } } cout << ans << '\n'; } }
결과
'문제풀이(BOJ) > 시뮬레이션(구현)' 카테고리의 다른 글
[백준 2526] 싸이클 (0) | 2020.01.09 |
---|---|
[백준 11507] 카드셋트 (0) | 2020.01.08 |
[백준 12759] 틱!택!토! (0) | 2020.01.08 |
[백준 2578] 빙고 (0) | 2020.01.06 |
[백준 1526] 가장 큰 금민수 (0) | 2020.01.06 |