[백준 2170] 선 긋기(Python)

잇프제들은 선 잘 긋는다던데.. 난 아니에요ㅎㅎ~

 

 

문제 링크 : https://www.acmicpc.net/problem/2170

2170번: 선 긋기

 

문제

매우 큰 도화지에 자를 대고 선을 그으려고 한다. 선을 그을 때에는 자의 한 점에서 다른 한 점까지 긋게 된다. 선을 그을 때에는 이미 선이 있는 위치에 겹쳐서 그릴 수도 있는데, 여러 번 그은 곳과 한 번 그은 곳의 차이를 구별할 수 없다고 하자.

이와 같은 식으로 선을 그었을 때, 그려진 선(들)의 총 길이를 구하는 프로그램을 작성하시오. 선이 여러 번 그려진 곳은 한 번씩만 계산한다.

입력

첫째 줄에 선을 그은 횟수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점의 위치 x, y (-1,000,000,000 ≤ x < y ≤ 1,000,000,000)가 주어진다.

출력

첫째 줄에 그은 선의 총 길이를 출력한다.

 

---

풀이 접근 방법 

 

선을 그을 때 나올 수 있는 모양에 대해서 고민해봤다.

 

이 부분은 그냥 머리 쥐어싸낸 고생의 흔적이니,, 해답이 보고 싶은 분들은 밑으로 넘어가주세욥..

 

 

제일 처음 들어오는 선을 기준으로 삼고 다음 들어오는 점들이 기존의 선에 포함되는 지와 크기 비교로 start, end 를 갱신해주면서 문제를 해결하려고 했다.

 

3% 에서 오류나고,, 고치고,,

50%에서 오류나고,, 고치고,, 

53% 에서 오류나고,, ☠️

 

53% 에서 오류난 코드는 다음과 같다. (해당 코드는 잘못된 풀이입니당)

import sys
input = sys.stdin.readline

n = int(input())
lines = []
ans = 0

for _ in range (n) :
    lines.append(tuple(map(int, input().split())))

#초기 점들을 기준
start,end = lines[0]

for i in range(1,n) :
    x,y=lines[i]

    #1번 경우
    if x <= start and y <= end :
        start = x
    # 2번 경우
    elif x >= start and y >= end :
        end = y
    # 3번 경우
    elif x >= start and y <= end :
        pass #start, end 그대로
    # 4번 경우 (아예 포함 x)
    elif x > end or y < start :
        ans += (end-start)
        start, end = x, y
    

ans += (end - start)
print(ans)

 

 

왜 왜 왜 왜 틀렸지?????? 

백준 게시판에 있는 반례도 다 돌려봤는데 왜왜왜왜?!

 

 

👑갓정우👑가 보내준 반례 덕분에 원인을 찾았다. 

4
20 70
10 60
0 50
-3001 -3000

answer : 71
내 코드 output : 3071 ㅋ

 

이 테스트 케이스에 대해서 start 는 -3001이 되고 end는 70이 되어버리는 문제가 발생한다. (겹치는 부분으로 처리해버림)

 

하 문제를 다시 천천히 읽어보장.. 

x는 항상 y보다 작거나 같다.

그렇다면 x를 기준으로 sort()를 해주고 이를 초기의 x, y값을  start,end 로 기준으로 삼아주면

그 뒤에 오는 값들은 무조건 start 보다 항상 크다.

sort()가 있어야 풀 수 있는 문제다..

 

 x 가 end 보다 작거나 같다면 무조건 기존의 선과 겹치는 경우이다!

그렇기 때문에 x는 비교할 필요 없이 y와 end값만 비교해서 큰 값을 end로 갱신하면된다.

 

x가 end 보다 크다면? 무조건 겹치지 않는 경우이다!! 

그렇기 때문에 기존의 start, end 값의 차이를 ans 에 더해주고 x,y를 새로운 start, end 로 갱신해주면된다.

 

ㅇㄴ 어렵..  sort()를 해야하는 이유를 딱 알았다..

 

정답 코드 🎯

import sys
input = sys.stdin.readline

n = int(input())
lines = []
ans = 0

for _ in range (n) :
    lines.append(tuple(map(int, input().split())))


# 정렬을 해주면 start는 비교할 필요가 없음
lines.sort()

# start가 가장 작은 점을 기준으로
start,end = lines[0]


for i in range(1,n) :
    x,y=lines[i]

    # 겹치는 경우
    if x <= end :
        end = max(y, end)
    # 아예 겹치지 않는 경우
    else :
        ans += (end - start) # 기존의 차이를 더해주고
        start, end = x, y # 시작,끝점 새롭게 업데이트
    
ans += (end - start)
print(ans)

 

 

그리고 이 문제의 선 긋기 횟수(N)가 최대 백만번이기 때문에 sys 모듈을 써서 input() 값을 입력받아야 백준 사이트에서 ps가 뜬다!!!

테케 개수가 넘 많을 때는 sys 모듈을 활용해보자 ✔️

 

 

 

1일 1문제 풀이 인증 완 🔥 

역시 갓생의 시작은 알고리즘으로부터.. 덕분에 매일 뿌듯함 🧗‍♂️