Platforme

# https://dmoj.ca/problem/crci07p1

# TODO : 플랫폼 위치 저장 후, 층수대로 정렬하기

count = int(input())
before_sort = []
altitude = []
horizontal_coordinates = []

for i in range(count):
    platform = list(map(int,input().split(" ")))
    before_sort.append(platform)

new_platforms = sorted(before_sort,key=lambda x:x[0])

for i in range(count):
    altitude.append(new_platforms[i][0])
    horizontal_coordinates.append(new_platforms[i][1:3])
    

# TODO : 플랫폼 위치가 겹치는지 확인하기

def check_scope(coordinate_list,target):
    if coordinate_list[0] < target and coordinate_list[1] > target:
        return True
    return False

# main

pillars = 0

for i in range(count):
    if i == 0:
        pillars += altitude[i] * 2
    if i != 0:
        for j in range(i-1,-1,-1):
            if check_scope(horizontal_coordinates[j],horizontal_coordinates[i][0]) or horizontal_coordinates[j][0] == horizontal_coordinates[i][0]:
                pillars += altitude[i]- altitude[j]
                break
            else:
                if j == 0:
                    pillars += altitude[i]
        
        for j in range(i-1,-1,-1):   
            if check_scope(horizontal_coordinates[j],horizontal_coordinates[i][1]) or horizontal_coordinates[j][1] == horizontal_coordinates[i][1]:
                pillars += altitude[i]- altitude[j]
                break
            else:
                if j == 0:
                    pillars += altitude[i]

print(pillars)

 

이 문제는 입력으로 들어올 수 있는 모든 경우의 수를 고려하지 못하고 코드를 짜는 바람에 그걸 찾아내느라 다소 시간이 걸렸다.

문제에서 해당 플랫폼의 아랫층이 있는 경우 즉, 좌표 범위가 겹치는 상황에서는 그 아랫층까지의 높이를 제외하고 기둥을 세워야 하는데, 아래 그림과 같이 플랫폼의 경계가 맞닿을 경우는 좌표 범위가 다르다고 여겨 각각 기둥을 세우도록 한다.

플랫폼의 끝 좌표와, 다른 플렛폼의 시작 좌표가 같은 경우는 같은 축으로 고려하지 않는다.

따라서 플랫폼의 시작과 끝 좌표가, 다른 플랫폼의 범위 안에 들어가는지를 판단하는 함수를 작성할 때 '<'와 '>'를 사용하였다.

def check_scope(coordinate_list,target):
    if coordinate_list[0] < target and coordinate_list[1] > target:
        return True
    return False

여기까지는 괜찮았는데, 한가지 내가 고려하지 못한 점은..

 

이렇게 시작좌표-시작좌표가 일치하는 경우 and 끝좌표-끝좌표가 일치하는 경우를 생각하지 못해서 몇몇 테스트코드를 통과하지 못했다.

for i in range(count):
    if i == 0:
        pillars += altitude[i] * 2
    if i != 0:
        for j in range(i-1,-1,-1):
        #시작과 시작이 같은 경우의 조건 추가
            if check_scope(horizontal_coordinates[j],horizontal_coordinates[i][0]) or horizontal_coordinates[j][0] == horizontal_coordinates[i][0]:
                pillars += altitude[i]- altitude[j]
                break
            else:
                if j == 0:
                    pillars += altitude[i]
        
        for j in range(i-1,-1,-1):
        # 끝과 끝이 같은 경우의 조건 추가
            if check_scope(horizontal_coordinates[j],horizontal_coordinates[i][1]) or horizontal_coordinates[j][1] == horizontal_coordinates[i][1]:
                pillars += altitude[i]- altitude[j]
                break
            else:
                if j == 0:
                    pillars += altitude[i]

or 조건으로 해당 조건을 추가해주니 모든 테스트 통과!

 

---

그림 출처 : https://dmoj.ca/problem/crci07p1