[C] 가장 큰 낙하거리 찾기

www.notion.so/4-0ac2b7de9f1e47118283ed80f1557441

✔︎ 미션 4.가장 큰 낙하거리 찾기

✔︎ 미션 4 (난이도 최상).

1. 미션 제목

가장 큰 낙하거리 찾기

 

2. 지시문

상자들이 쌓여있는 방이 있습니다. 방이 오른쪽으로 90도 회전하여 상자들이 중력의 영향을 받아 낙하한다고 할 때, 낙하거리가 가장 큰 상자를 구하여 그 낙하거리를 출력하는 프로그램을 작성해 봅시다. 아래 그림에서 총 26개 상자가 회전 후, 오른쪽 그림과 같은 상태가 됩니다. A상자의 낙하거리가 7로 가장 크므로 7을 출력하면 됩니다. 회전 결과, B 상자의 낙하거리는 6이고, C상자의 낙하거리는 1입니다.

 

중력은 회전이 완료된 이후에 적용되며, 상자들은 모두 한쪽 벽면에 붙여진 상태로 쌓여 2차원의 형태를 이루며 벽에서 떨어져서 쌓인 상자는 없습니다. 입력으로는 첫 줄에 각 방의 가로 길이 N(2 ≤ N ≤ 100)과 방의 세로 길이 M(2 ≤ N ≤ 100)이 주어지며, 다음 줄에는 N개의 상자들이 쌓여있는 높이 H(0 ≤ H ≤ M)가 주어집니다. 가장 직관적인 방법은 MxN내의 모든 box에 대해서 낙하거리를 계산한 뒤 정렬 알고리즘을 사용하여 최댓값을 찾으면 되는 문제라고 생각할 수 있습니다. 이 방법은 시간 복잡도(Big O)가 얼마나 될 지 먼저 생각해봅시다. 그리고, 이보다 더 효율적인 방법으로 프로그램을 작성해봅시다. 완전한 프로그램을 작성하는 것이 힘들 경우에는 pseudo code로 작성해도 좋습니다. 다만 이 경우에는 최대한 자세히 적어야 합니다. 숫자를 입력 받는 부분은 따로 구현하지 않고 프로그램 내부에서 따로 선언하는 것으로 가정합니다.

 

예)

입력값:

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

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

 

출력값:

7 // 가장 큰 낙하거리

 

3. 핵심 개념

# 최대값찾기

 

나의 풀이

아이디어

벽에서 떨어져서 쌓여있는 상자는 없다는 조건이 있으니 높이 쌓여있으면서 왼쪽에 있는 블록일수록 더 많이 낙하할 가능성이 높습니다

즉 쌓여있는 블록에서 가장 많이 떨어질 블록은 꼭대기에 있는 블록일 것입니다.

 

1. 우선 첫 번째 단계로 맨 오른쪽 칸부터 +0으로 시작하여 숫자를 하나씩 늘려나가며 +n 표시를 해줍니다.

 

2. 블록들이 7, 4, 2, ... 층으로 쌓여있는데 자신의 오른쪽을 보고 자신과 높이가 같거나 더 높은 블록의 수를 체크해서 빼줍니다.

자신과 높이가 같거나 더 높은 블록에 의해서 회전했을 때 그 수만큼 덜 낙하하기 때문입니다.

 

3. 1번에서 더하기 한 값과 2번에서 뺀 값을 계산해줍니다. 이때 블록이 0개 쌓인 곳은 낙하할 블록이 없으므로 제외시켜줍니다.

정답은 맨 왼쪽 블록의 꼭대기에 있는 블록이 7만큼 낙하하여 최대 크기로 낙하한 것으로 나옵니다.

 

모든 블록의 낙하 거리를 계산하려면 회전 후 자신의 밑에 깔릴 블록의 수 X 자신의 위치(N X M) = **O(N^3)**의 복잡도가 나오지 않을까 생각된다.

 

하지만 모든 블록을 계산하지 않고 또한 회전 후 모습을 새로 그려야 하는 문제가 아닌 단순히 한 번의 회전과 하나의 출력 만을 요구하는 이 문제에서는 블록이 쌓인 개수만 고려하면 되므로 O(N^2)의 복잡도를 가질 것으로 생각됩니다.

 

#include<stdio.h>

int main(void) {
    int size[2] = {9, 8};
    int boxes[9] = {7, 4, 2, 0, 0, 6, 0, 7, 0};
    int calc[9];
    int width = size[0];

    for(int i = 0 ; i < width; i++) {
        int count = 0;
        // 위치에 따른 점수 부여 (+8 ~ +0)
        calc[i] = width - i - 1;

        // 자신의 오른쪽에 자신보다 높은 블록이 있는지 확인
        for(int j = i + 1; j < width; j++) {
            if(boxes[i] <= boxes[j]) {
                count++;
            }
        }

        // 자신의 오른쪽에 자신과 크기가 같거나 큰 블록의 개수만큼 빼기
        calc[i] -= count;
    }

    // 최대 낙하거리 확인
    int max = 0;
    for(int i = 0 ; i < width; i++) {
        // 최대 낙하거리 확인 및 높이가 0인 블록 패스
        if(max < calc[i] && boxes[i] != 0) {
            max = calc[i];
        }
    }
    printf("%d\n", max);
}