SWEA 13569 그래비티 풀이

https://swexpertacademy.com/main/talk/solvingClub/problemView.do?solveclubId=AYJ7KE5qKy8DFASv&contestProbId=AX7UNdWaadEDFAVm&probBoxId=AYJ7KE5qKzADFASv&type=USER&problemBoxTitle=list1&problemBoxCnt=5

SW Expert Academy

 

의도치 않게 오래걸린 문제였다.

일단 문제를 읽을때 굉장히 주의해야하는게 있는데

상자의 높이가 0부터 M까지라고 해놓고 M에 대한 조건을 주지 않았다는 점을 주의해야한다.

이 부분을 간과했다가 보이지 않는 tc에서 런타임에러가 떴다.

높이의 범위가 주어지지 않았으니

bucket을 만들때, 그리고 for문으로 탐색을 할때 주어진 값중에 제일 큰 값을 전체 높이로 해야 한다.

그래서 max(a)를 활용했다.

 

T = int(input())

for tc in range(1, 1+T):
    n = int(input())
    a = list(map(int, input().split()))

    array_bucket=[]
    for i in range(n):
        bucket = [0] * max(a)
        for j in range(a[i]):
            bucket[j] += 1
        array_bucket.append(bucket)
    # print(array_bucket)

    MAX = 0
    for i in range(n):
        for j in range(max(a)):
            if array_bucket[i][j]==1:
                cnt=0
                for k in range(n-1, i, -1):
                    if array_bucket[k][j]==0:
                        cnt +=1
                    else: cnt +=0

                    if cnt>MAX:
                        MAX = cnt
            else:
                continue


    print(f'#{tc} {MAX}')

밑의 3중 for문에 대한 설명을 하자면

일단 2중으로 돌면서 bucket의 값이 1인 것들만 확인한다.

y축 기준으로 밑에 있는 부분이 비어있으면(0이면) cnt에 1을 더한다,

비어있지 않으면(1이면) 0을 더한다.

 

내가 지금 선택한 칸 기준으로 아래 칸들이 비어있는 수만큼이 낙차가 되는거다

B, C에서 해도 같은 결과가 나온다.