SWEA 그래비티 풀이2

https://gkim1011.tistory.com/9

SWEA 13569 그래비티 풀이

 

저번에는 문제에서 주어진 그림을 참고하여,

블럭 하나하나를 2차배열 bucket에 담은 후 중력 작용을 확인했었다.

하지만 굳이 bucket으로 안풀어도 되는 문제였다.

 

일단 생각해야 하는 것은

낙차가 가장 크게 생길 수 있는 지점은 블럭 탑의 꼭대기이라는 것이다.

그렇기 때문에 블럭 탑에서 낙차의 max 값은 어차피 꼭대기 블럭 하나의 낙차와 같다.

2중 배열을 돌면서 모든 블럭의 낙차를 계산하지 말고, 그 탑의 꼭대기 블럭의 낙차를 계산 후, max값을 찾아주면 된다.

 

2중 for문을 쓸건데, 첫번째 for문에서는 낙차 값을 초기화시켜준다.

T = int(input())

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

    MAX = 0
    for t in range(N - 1, -1, -1):
        cnt = 0

지금 쓰면서 생각한건데 굳이 range를 거꾸로 갈 필요는 없다.

그냥 range(N)써도 된다는 뜻.

        for s in range(t+1, N):
            if arr[t]>arr[s]:
                cnt+=1
        if cnt>MAX:
            MAX = cnt

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

내가 낙차 찾고자 하는 탑의 다음꺼부터 끝까지중에, 내 탑보다 크기가 작으면 낙차+1, 아니면 +0을 하면 된다.

그리고 마지막엔 MAX값과 비교하기

 

이 방법을 쓰면 저번 풀이처럼 M의 길이에 따른 영향을 받지 않아도 된다.

그리고 2중 for문이기 때문에 시간도 단축된다.

 

 

전체코드)

T = int(input())

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

    MAX = 0
    for t in range(N - 1, -1, -1):
        cnt = 0
        for s in range(t+1, N): # 지금 확인하고자 하는 다음칸~끝칸까지
            if arr[t]>arr[s]: #높이가 더 높아야 낙차가 생김
                cnt+=1
        if cnt>MAX:
            MAX = cnt

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