[코드트리 챌린지] 1주차

---

실력진단 결과

코드트리 1주차 실력진단 결과

---

오늘의 학습

+1 -1 Technique

다음 문제는 어떻게 해결해 볼 수 있을까요?

1개의 선분이 주어졌을 때, x = k 직선과 만나는 서로 다른 선분의 수는 몇 개인지를 판단하는 프로그램을 작성해보세요. 단, 주어지는 x 좌표는 모두 다름을 가정해도 좋습니다.

예로, 다음 그림에서의 답은 2가 됩니다.

눈으로 봤을 때는 지극히 당연히 2개라는 것을 알 수 있지만, 이를 컴퓨터가 계산하기 쉽게 나타내기 위해서는 어떻게 해야 할까요?

바로 선분마다 시작점에는 +1, 끝나는 지점에는 -1을 적은 뒤, 빨간선 앞에 있는 점들에 적혀있는 숫자들을 전부 더해주면 됩니다. 이 의미는 곧 앞에 시작, 끝 지점이 전부 다 있는 선분들은 0으로 처리하고, 단 시작점만 나온 선분들에 대해서는 +1을 진행한다는 뜻입니다.

이 점을 활용하면 주어지는 모든 선분 N개를 각각 2개의 시작점, 끝점으로 구분하여 총 2N개의 점으로 나눠 이를 x좌표 순으로 오름차순 정렬한 뒤, x = k보다 커지기 직전까지의 숫자를 전부 더하는 식으로 진행해볼 수 있습니다.

이렇듯 N개의 선분을 2개의 시작, 끝 정점으로 나눠 각각 +1, -1 가중치를 줘서 x가 증가하는 순서대로 정렬하는 방법을 +1 -1 Technique이라 부릅니다.