[파이썬] Gravity

by SW expert academy

 

상자들이 쌓여있는 방이 있다. 방이 오른쪽으로 90도 회전하여 상자들이 중력의 영향을 받아 낙하한다고 할 때, 낙차가가장 큰 상자를 구하여 그 낙차를 출력하여 보자.

 

위의 예시에서 총 26개의 상자가 회전 후, 오른쪽 그림의 상태가 된다. A상자의 낙차가 7로 가장 크므로 7을 출력하면 된다. 회전 결과, B 상자의 낙차는 6, C 상자의 낙차는 1이다.

 

중력은 회전이 완료된 후 적용된다. 상자들은 모두 한쪽 벽면에 붙여진 상태로 쌓여 2차원의 형태를 이루며 벽에서 떨어져서 쌓인 상자는 없다.

 

입력

첫 번째 줄에 test case의 수 T(1 <= T <= 100)가 주어진다. 각 케이스의 첫째 줄에 방의 가로 길이 N(2 <= N <= 100)과 방의 세로 길이 M(2 <= M <= 100)이 주어진다. 다음 줄에는 N개의 상자들이 쌓여 있는 높이 H(0 <= H <= M)가 주어진다. 

 

입력 예시

1   // 테스트 케이스 T의 개수

9 8   // 방의 가로 길이 N, 방의 세로 길이 M

7 4 2 0 0 6 0 7 0   // 상자들이 쌓여 있는 높이

 

출력

낙차가 가장 큰 값을 출력 한다.

 

출력 예시

7

 

🎗 나의 풀이

 

# Gravity
T = int(input())  # 테스트 케이스 수
for tc in range(1, T + 1):
    N, M = map(int, input().split())  # 가로, 세로
    room = [[0] * M for _ in range(N)]    # 방 넓이
    H = list(map(int, input().split()))  # N개의 상자들이 쌓여 있는 높이
    result = 0                            # 낙차가 가장 큰 값

    for i in range(N):                    # 방에 상자 쌓기(1로 표현)
      for j in range(H[i]):
        room[i][j] = 1            

    # 각 상자의 낙차 구하기
    for i in range(N):  # 가로
      for j in range(M):  # 세로
        if room[i][j] == 1:  # 박스일 때
          max_value = 0
          for k in range(i + 1, N):   # 가로
            if room[k][j] == 0:       # 박스가 없으면 낙차 1 증가
              max_value += 1
          if result < max_value:
            result = max_value

    print(result)

 

입력받은 가로, 세로로 이차원 리스트 room을 만든다.

이차원 리스트 room에 상자가 있는 위치에 1을 넣는다.

모든 상자들의 낙차를 구한다. 구한 낙차 중 가장 큰 값을 출력한다.

 

# Gravity
T = int(input())  # 테스트 케이스 수
for tc in range(1, T + 1):
    N, M = map(int, input().split())  # 가로, 세로
    room = [[0] * M for _ in range(N)]    # 방 넓이
    H = list(map(int, input().split()))  # N개의 상자들이 쌓여 있는 높이
    result = 0                            # 낙차가 가장 큰 값

    for i in range(N):                    # 방에 상자 쌓기(1로 표현)
      #for j in range(H[i]):
      j=H[i]
      room[i][j] = 1            

    # 각 상자의 낙차 구하기
    for i in range(N):  # 가로
      j=H[i]
      max_value = 0
      for k in range(i + 1, N):   # 가로
        if room[k][j] == 0:       # 박스가 없으면 낙차 1 증가
          max_value += 1
      if result < max_value:
        result = max_value    

    print(result)

 

위의 풀이와 다르게 가장 끝에만 상자를 쌓았다.

가로 당 마지막 상자의 낙차를 구했다.

 

# 해설 풀이(C 언어)

 

#include<stdio.h>
#define EMPTY 0
#define BOX 1

int main() {
	int i, j, k;
	int testCase;
	int T;
	int room[100][100];
	int roomWidth, roomHeight;
	int boxHeight;
	int maxFallen;
	int countEmptySpace;

	scanf_s("%d", &testCase);

	for (T = 0; T < testCase; T++) {
		scanf_s("%d%d", &roomWidth, &roomHeight);

		//초기화
		for (i = 0; i < roomWidth; i++) {
			for (j = 0; j < roomHeight; j++) {
				room[i][j] = EMPTY;
			}
			maxFallen = 0;
		}
		for (i = 0; i < roomWidth; i++) {
			// 방에 상자 채우기
			scanf_s("%d", &boxHeight);
			for (j = 0; j < boxHeight; j++) {
				room[i][j] = BOX;
			}
		}

		// 각 상자의 낙차를 구한다.
		for (i = 0; i < roomWidth; i++) {
			for (j = 0; j < roomHeight; j++) {
				// room[i][j]가 박스일때 빈칸의 개수를 세서 낙차 구하기
				if (room[i][j] == BOX) {
					countEmptySpace = 0;
					for (k = i + 1; k < roomWidth; k++) {
						if (room[k][j] == EMPTY)
							countEmptySpace += 1;
					}
					// 이전에 구한 낙차보다 현재 낙차가 크다면 업데1이트
					if (countEmptySpace > maxFallen)
						maxFallen = countEmptySpace;
				}
			}
		}
		printf("%d\n", maxFallen);
	}
}

 

모든 상자들의 낙차를 구하는 코드

 

#include<stdio.h>
#define EMPTY 0
#define BOX 1

int main() {
	int i;
	int testCase, T;
	int roomWidth, roomHeight;
	int maxFallen;
	int room[100][100] = { EMPTY, };
	int boxTop[100] = { 0, };
	int countEmptySpace;
	scanf_s("%d", &testCase);

	for (T = 0; T < testCase; T++) {
		scanf_s("%d%d", &roomWidth, &roomHeight);
		maxFallen = 0;
		//초기화
		for (i = 0; i < roomWidth; i++) {		// 방에 상자들을 채운다
			scanf_s("%d", &boxTop[i]);
			for (int j = 0; j < boxTop[i]; j++) {
				room[i][j] = BOX;
			}
			
		}
		// 각 상자 열(column)의 가장 위에 있는 상자의 낙차를 구한다.
		for (i = 0; i < roomWidth; i++) {
			if (boxTop[i] > 0) {
				countEmptySpace = 0;
				for (int j = i + 1; j < roomWidth; j++) {
					// room[i][j]가 박스일때 빈칸의 개수를 셈으로서 낙차를 구한다.
					if (room[j][boxTop[i] - 1] == EMPTY) {
						countEmptySpace += 1;
					}
				}
				// 이전에 구한 낙차보다 현재 낙차가 크다면 업데이트
				if (countEmptySpace > maxFallen)
					maxFallen = countEmptySpace;
			}
		}
		printf("%d\n", maxFallen);
	}
}

 

각 열의 마지막 상자의 낙차만 구함