본문 바로가기
728x90

스위핑3

[python] 백준 2283 구간 자르기 https://www.acmicpc.net/problem/2283 2283번: 구간 자르기 1번째 줄에 정수 N, K(1 ≤ N ≤ 1,000, 1 ≤ K ≤ 1,000,000,000)가 주어진다. 2~N+1번째 줄에 각 구간의 왼쪽 끝점과 오른쪽 끝점의 위치가 주어진다. 양 끝점의 위치는 0 이상 1,000,000 이하의 정수이다. www.acmicpc.net 문제 해결 리스트 인덱스를 x좌표로 하여 막대의 좌표 ( ex: (3,7)이면 vertical[3:7]에 +1씩 더해서 길이를 측정할 수 있도록 한다.)로 나타낸다. 원하는 만큼의 길이(k)가 안나오면 끝점(r)를 1씩 높여서 해당되는 길이만큼 증가시키고 그보다 크게 나오면 시작점(l)를 1씩 높여서 해당되는 길이만큼 줄이면서 원하는 값이 나오는.. 2023. 6. 26.
[python] 백준 2170 선 긋기 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)가 주어진다. www.acmicpc.net 문제 해결 n과 x, y의 범위가 매우 크기 때문에 리스트를 만들어서 0,1로 색칠하기를 할 수는 없다. 그러면 주어진 범위를 가지고 한번에 길이 범위를 수정해야 한다. 결국 리스트 안에 범위를 다 넣고 lowerbound를 오름차순 한 다음 다음 범위와 연결 되는지 안되는지 확인하면 끝 단 python3로는 시간초과가 뜨고 pypy3로 성공했다. (n이 지나치게 .. 2023. 4. 8.
[python] 백준 1911 흙길 보수하기 https://www.acmicpc.net/problem/1911 1911번: 흙길 보수하기 어젯밤 겨울 캠프 장소에서 월드 본원까지 이어지는, 흙으로 된 비밀길 위에 폭우가 내려서 N (1 2023. 4. 5.
728x90