완전탐색 | 1206. [S/W 문제해결 기본] 1일차 - View

문제

 

1206. [S/W 문제해결 기본] 1일차 - View

SW Expert Academy

 

빌딩에서 왼쪽과 오른쪽으로 창문을 열었을 때. 양쪽 모두 2 이상의 거리가 확보되어야 조망권이 확보된다고 한다.

빌딩의 높이에 대한 정보가 주어질 때 조망권이 확보된 세대의 수를 반환하라.

 

 

입력

• 총 10개의 테스트 케이스가 주어짐
• 각 테스트 케이스의 첫 줄은 건물의 개수 N  (4 ≤ N ≤ 1000)
• 그 다음 줄은 N개의 건물의 높이 (0 ≤ 각 건물의 높이 ≤ 255)
• 맨 왼쪽 두 칸과 맨 오른쪽의 두 칸은 높이가 0임

10
0 0 254 185 76 227 84 175 0 0

 

출력

• #테스트케이스번호 조망권이 확보된 세대의 수

#1 111

 

 

풀이

for k in range(10):
    N = int(input().strip())
    buildings = list(map(int, input().split()))
    count = 0

    for i in range(2, N - 2):
        # 현재 건물 기준으로 양옆 두 칸 중 최대 높이 찾기
        max_side = max(buildings[i-2], buildings[i-1], buildings[i+1], buildings[i+2])
        
        # 현재 건물이 양옆보다 높을 때만 조망권 발생
        if buildings[i] > max_side:
            count += buildings[i] - max_side

    print(f"#{k+1} {count}")

 

 

해당 문제는 완전 탐색 문제이다.

양옆 2개씩 총 4개의 빌딩이 현재의 빌딩보다 높이가 낮아야 조망권이 확보된다.

 

맨 왼쪽 두 칸과 맨 오른쪽의 두 칸은 높이가 0이라고 했으므로 이 부분은 반복문 범위에서 제외하고,

그 사이의 건물만 확인하면 된다.

 

양옆 4개의 빌딩 중 가장 큰 것을 현재와 빌딩과 비교했을 때, 현재의 건물이 더 크면 조망권이 확보되는 것을 알 수 있다.