Dalin's Archive

문제!! 풀이 🌷 통나무의 세로로 입력으로 들어오지만 가로만 봐주면 된다. 선 긋는 스위핑 문제처럼 풀면 되는 것이었다. 그 문제 포스팅은 여기..ㅎㅎ 어려웠던 점 🦄 처음에는 통나무의 가로, 세로 좌표 둘 다 봐줘야 하는 줄 알았다.. 좌표는 10^9까지 있다고 하는데, 가로 세로를 고려해서 2차원으로 만들면 너무 클 것 같은데... ㅠ 어떻게 하나 고민했다. 그런데 가로!!!만 봐주면 되는 것이었다. 점프하면 되니까 세로는 볼 필요가 없었다. 원래 입력 받은 리스트를 정렬해서, 그 순서가 망가진다.. 그러니까 원래 인덱스를 가지고 있어야 한다! 그래야 어떤 통나무랑 다른 통나무랑 이어져있는지 체크가 가능하니까!!! 코드 🐸 import sys input = sys.stdin.readline N, Q ..

문제로 가기 정렬하고 쭉 ~ 한번 보면 되는 스위핑 문제!! 정렬한 후에 (출발지가 앞쪽인 순서, 출발지가 같으면 도착지가 앞쪽일 수록 앞에) 쭉~ 보면서 두 노선씩 비교한다. a_route는 처음 노선으로 초기화하고 시작하고, b_route는 그 다음 노선부터 끝까지 쭉 본다. 만약 a, b 노선이 겹친다면 합쳐서 새로운 노선으로 만든다! 이때 요금은 더 낮은 쪽을 따른다. 출발점이 더 나중에어도, 도착점이 더 이른 노선이 있을 수도 있다. 노란 색 노선, 빨간 색 노선을 비교할 때는.. 일단 겹치니까 a_route를 업데이트하는데, 'a_route = (a_route[0], max(a_route[1], b_route[1]), min(a_route[2], b_route[2]))'에서 'max(a_rou..

문제 보러가기 접근 🍁 쭉~ 입력을 받은 후에 정렬을 했다. 정렬을 하는 게 매우 중요하다..!! start와 end는, 다른 선들과 겹치지 않는 선은 계산을 끝내고, (다른 선들과 겹칠 가능성을 가진) 당시에 가장 긴 선을 의미한다. 맨 처음 시작점, 도착점을 각각 start, end에 대입했다. 그 다음부터 각각의 시작점, 도착점과 start, end를 비교해 보면 아래 그림의 세 가지 경우 중 하나가 된다. (정렬을 했으니까 항상 그 시점의 시작점보다 start가 작거나 같을 것이다. 그래서 아래 세 가지 경우만 있다.) 1) 두 선이 겹치고, 그 때 꺼낸 도착점이 end보다 뒤에 있는 경우. 그러면 start는 그대로 두고, end는 그때 꺼낸 도착점으로 업데이트한다. 2) 두 선이 겹치고, 그 ..