[백준] 22866 - 탑 보기

링크

https://www.acmicpc.net/problem/22866

문제

일직선으로 다양한 높이의 건물이 총 $N$개가 존재한다.
각 건물 옥상에서 양 옆에 존재하는 건물의 옆을 몇 개 볼 수 있는지 궁금해졌다.
$i$번째 건물 기준으로 $i - 1$, $i - 2$, ...,
$1$번째 건물은 왼쪽에, $i + 1$, $i + 2$, ...,
$N$번째 건물은 오른쪽에 있다. 각 건물 사이의 거리는 다 동일하다.

현재 있는 건물의 높이가 $L$이라고 가정하면 높이가 $L$보다 큰 곳의 건물만 볼 수 있다.

바라보는 방향으로 높이가 $L$인 건물 뒤에 높이가 $L$이하인 건물이 있다면 가려져서 보이지 않는다.

각 건물에서 볼 수 있는 건물들이 어떤것이 있는지 구해보자.

입력

첫번째 줄에 건물의 개수 $N$이 주어진다.

두번째 줄에는 $N$개의 건물 높이가 공백으로 구분되어 주어진다.

출력

 
$i(1 \le i \le N)$번째 건물에서 볼 수 있는 건물의 개수를 출력한다.

만약 볼 수 있는 건물의 개수가 1개 이상이라면 $i$번째 건물에서 거리가 가장 가까운 건물의 번호 중 작은 번호로 출력한다.

풀이

[1] 나이브한 접근

z번째 빌딩보다 왼쪽에 있는 빌딩 중 높은 빌딩(y)을 찾는다.
y번째 빌딩보다 왼쪽에 있는 빌딩 중 높은 빌딩(x)을 찾는다.
x번째 빌딩보다 왼쪽에 있는 빌딩 중 높은 빌딩(w)을 찾는다.

위를 반복하면 z번째 건물에서 볼 수 있는 왼쪽 건물들을 알 수 있다.

[2] DP 관점

w > x > y > z 인 건물이 순서대로 주어 졌을 때,
각 건물에서 볼 수 있는 왼쪽 건물의 수는 아래 표와 같다.

만약 중간에 가장 높은 건물이 추가 된다면 어떻게 될까?

위의 그림과 같이 y와 z의 결과가 바뀌게 된다.

특정 빌딩(z) 보다 왼쪽에 높은 빌딩(y)이 있는 경우,
높은 빌딩(y)의 dp값 +1이 특정 빌딩(x)의 dp값이 된다.

[3] 결과

왼쪽 빌딩의 결과를 구한 것과 같이, 오른쪽 빌딩의 결과 또한 DP로 구한다.
출력 조건 중 아래와 같은 문구가 있다.
만약 볼 수 있는 건물의 개수가 1개 이상이라면 $i$번째 건물에서 거리가 가장 가까운 건물의 번호 중 작은 번호로 출력한다.
DP 테이블이 갱신 되는 경우에 높은 빌딩(y)의 인덱스를 저장해두면 된다.

// 왼쪽 빌딩 확인 코드 중 일부
if(buildings[j] > buildings[i]){
    dp[i][0] = dp[j][0]+1;
    dp[i][2] = j+1; // 인덱스 저장
    break;
}

// 오른쪽 빌딩 확인 코드 중 일부
if(dp[i][0] == 0 || (i - dp[i][2]+1) > (j-i)){
    dp[i][2] = j+1;
}

[4] 최적화

특정 빌딩(z) 보다 왼쪽에 높은 빌딩(y)이 있는 경우는 반복문을 통해 알 수 있다.
단, 특정 빌딩(z)이 왼쪽에 있는 모든 빌딩 보다 높은 빌딩이라면 어떻게 될까?
0번째 빌딩까지 높이를 다 확인해야 한다!

이는 0부터 i번째 빌딩까지 높이를 확인할 때, 가장 높은 빌딩의 높이를 변수에 저장해두면 최적화 할 수 있다.

if(max < buildings[i]){
    max = buildings[i];
    continue;
}

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ_22866_탑보기 {

    static int N;
    static int[] buildings;
    static int[][] dp;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 입력| N, buildings
        N = Integer.parseInt(br.readLine()); 
        StringTokenizer stk = new StringTokenizer(br.readLine());

        buildings = new int[N];
        for(int i=0; i<N; i++)  buildings[i] = Integer.parseInt(stk.nextToken());

        // 초기화| dp
        dp = new int[N][3]; // [i][0]: i기준 왼쪽 빌딩, [i][1]: i기준 오른쪽 빌딩, [i][2]: 가장 가까운 빌딩

        // 왼쪽 빌딩 확인
        int max = buildings[0];
        for(int i=1; i<N; i++){
            if(max < buildings[i]){
                max = buildings[i];
                continue;
            }

            for(int j=i-1; j>=0; j--){
                if(buildings[j] > buildings[i]){
                    dp[i][0] = dp[j][0]+1;
                    dp[i][2] = j+1;
                    break;
                }
            }
        }

        // 오른쪽 빌딩 확인
        max = buildings[N-1];
        for(int i=N-2; i>=0; i--){
            if(buildings[i] > max){
                max = buildings[i];
                continue;
            }

            for(int j=i+1; j<N; j++){
                if(buildings[i] < buildings[j]){
                    dp[i][1] = dp[j][1]+1;

                    if(dp[i][0] == 0 || (i - dp[i][2]+1) > (j-i)){
                        dp[i][2] = j+1;
                    }

                    break;
                }
            }
        }

        // 결과 출력
        StringBuilder sb = new StringBuilder();
        for(int i=0; i<N; i++){
            int sum = dp[i][0] + dp[i][1];

            sb.append(sum).append(" ");
            if(sum != 0) sb.append(dp[i][2]);
            sb.append("\n");
        }

        System.out.println(sb);
    }
}