개발 블로그

문제

도시에는 N개의 빌딩이 있다.

빌딩 관리인들은 매우 성실 하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어한다.

i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으로만 볼 수 있다.

i번째 빌딩 관리인이 볼 수 있는 다른 빌딩의 옥상 정원은 i+1, i+2, .... , N이다.

그런데 자신이 위치한 빌딩보다 높거나 같은 빌딩이 있으면 그 다음에 있는 모든 빌딩의 옥상은 보지 못한다.

예) N=6, H = {10, 3, 7, 4, 12, 2}인 경우

             = 
 =           = 
 =     -     = 
 =     =     =        -> 관리인이 보는 방향
 =  -  =  =  =   
 =  =  =  =  =  = 
10  3  7  4  12 2     -> 빌딩의 높이
[1][2][3][4][5][6]    -> 빌딩의 번호

• 1번 관리인은 2, 3, 4번 빌딩의 옥상을 확인할 수 있다.
• 2번 관리인은 다른 빌딩의 옥상을 확인할 수 없다.
• 3번 관리인은 4번 빌딩의 옥상을 확인할 수 있다.
• 4번 관리인은 다른 빌딩의 옥상을 확인할 수 없다.
• 5번 관리인은 6번 빌딩의 옥상을 확인할 수 있다.
• 6번 관리인은 마지막이므로 다른 빌딩의 옥상을 확인할 수 없다.

따라서, 관리인들이 옥상정원을 확인할 수 있는 총 수는 3 + 0 + 1 + 0 + 1 + 0 = 5이다.

입력

• 첫 번째 줄에 빌딩의 개수 N이 입력된다.(1 ≤ N ≤ 80,000)
• 두 번째 줄 부터 N+1번째 줄까지 각 빌딩의 높이가 hi 입력된다. (1 ≤ hi ≤ 1,000,000,000)

출력

• 각 관리인들이 벤치마킹이 가능한 빌딩의 수의 합을 출력한다.

접근 방법

이 문제는 주어진 상황만 완전탐색으로 잘 구현하면 되는 문제였다. 비교적 쉬운 문제였는데 왜 정답률이 낮나 하고 보니 자료형이 잘못되어 틀린 경우가 많을 것 같았다. (본인도 첫 제출에 틀렸다.)

주어진 h의 범위는 1<=h<=1,000,000,000 이다. 

Java의 정수 자료형 및 범위를 생각해보자.

만약 N이 80,000(최대값)일 때 높이가 차례로 1,000,000,000(1억)부터 1씩 낮아진다고 하면

1억 + (1억-1) +(1억-2) + ... + (1억-79,000) 이 될 것이다. 이 경우엔 20억이 훌쩍 넘기 때문에 answer을 int 형으로 선언하면 틀리게 된다. 자료형을 주의하자.

import java.util.*;
public class BOJ_6198_옥상정원꾸미기 {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        long[] heightArr = new long[N];
        long ans = 0;

        for(int i = 0; i<N; i++){
            heightArr[i] = sc.nextInt();
        }
        for(int i = 0; i<N-1; i++) {
            long curHeight = heightArr[i];
            for(int j = i+1; j<N; j++){
                long nextHeight = heightArr[j];
                if(curHeight<=nextHeight) break;
                else ans++;
            }
            //System.out.println(ans);
        }
        System.out.println(ans);

    }
}