문제
m행 n열로 이루어진 그리드가 주어진다. 일부 칸에는 박스가 들어 있다. 모든 박스가 더 이상 움직일 수 없을 때 까지 아래로 움직인다면, 박스는 쌓여진 상태가 된다.
그림 (a)의 그리드의 크기는 5행 4열이고, 7칸에는 박스가 들어있다. 모든 박스가 계속해서 아래로 움직이면, 그림 (b)와 같이 변하게 된다.
박스가 움직인 거리는 바닥에 쌓이기 전 까지 이동한 칸의 개수이다. 예를 들어, 맨 왼쪽 열에서 가장 위에 있는 박스가 움직인 거리는 2이다. 모든 박스가 이동한 거리 (각 박스가 이동한 거리의 합) 을 구하는 프로그램을 작성하시오. 위의 예제에서 박스 7개가 움직인 거리는 8이다.
입력
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 m과 n이 주어진다. (1 ≤ m, n ≤ 100) 다음 m개 줄에는 그리드의 각 행의 정보를 나타내는 n개의 정수가 주어진다. 그리드 첫 행부터 마지막 행까지 순서대로 주어진다. 박스가 들어있는 칸은 1로, 다른 칸은 0으로 주어진다. 각 정수 사이에는 공백이 하나 주어진다.
출력
각 테스트 케이스마다 입력으로 주어진 그리드에서 모든 박스가 이동한 거리를 출력한다.
💻 예제 입력
3
5 4
1 0 0 0
0 0 1 0
1 0 0 1
0 1 0 0
1 0 1 0
3 3
1 1 1
1 1 1
0 0 0
5 6
1 0 1 1 0 1
0 0 0 0 0 0
1 1 1 0 0 0
0 0 0 1 1 1
0 1 0 1 0 1💻 예제 출력
8
6
16풀이
박스가 이동한 거리는 현재 박스가 있는 위치보다 아래 칸에 있는 모든 빈칸의 개수와 같음.
따라서 box[j][i] 가 1이라면, 즉 박스가 있다면, 그 아래 칸부터 존재하는 모든 0을 세어주면 이동거리를 구할 수 있음.
주의할 점은 만약 예시의 그림(a)와 같은 박스가 주어졌을 때, 배열에 이 값들을 담으면 맨 위 박스의 인덱스가 0이고, 맨 아래 박스의 인덱스가 m이 됨.
→ 따라서 box[0][i]에 박스가 있다면, 그 아래인 box[1][i], box[2][i] … box[m][i] 에서 0을 세어주면 됨.
C++ 소스코드
#include <iostream>
using namespace std;
int main(void) {
int T, m, n;
cin >> T;
while (T--)
{
int count = 0; // 0의 개수 (이동 거리)
int box[100][100]; // 박스
cin >> m >> n;
// 배열에 입력 받기
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++)
cin >> box[i][j];
}
// 이동거리 계산
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++)
{
// 박스가 놓여있다면?
if (box[j][i] == 1)
{
// 현재위치 아래 칸부터 끝까지 0 개수 세기 (이동거리)
for (int k = j+1; k < m; k++) {
if (box[k][i] == 0)
count++;
}
}
}
}
cout << count << "\n";
}
}Java 소스코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
while (T-- != 0)
{
String[] s = br.readLine().split(" ");
int m = Integer.parseInt(s[0]);
int n = Integer.parseInt(s[1]);
int count = 0; // 0의 개수 (이동거리)
int[][] box = new int[m][n]; // 박스
// 배열에 입력 받기
for (int i = 0; i < m; i++) {
s = br.readLine().split(" ");
for (int j = 0; j < n; j++)
box[i][j] = Integer.parseInt(s[j]);
}
// 이동거리 계산
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++)
{
// 박스가 놓여있다면?
if (box[j][i] == 1)
{
// 현재위치 아래 칸부터 끝까지 0 개수 세기 (이동거리)
for (int k = j+1; k < m; k++) {
if (box[k][i] == 0)
count++;
}
}
}
}
System.out.println(count);
}
}
}