본문 바로가기
728x90

정렬34

[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] 백준 8980 택배 https://www.acmicpc.net/problem/8980 8980번: 택배 입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이 www.acmicpc.net 문제 해결 택배를 옮길 수 있는 최대 개수를 구하는 문제 어떤 택배가 더 가중치 있고 하지 않으므로 그냥 많이 옮기면 된다. 그러면 가까운 거리를 많이 이용하면 좋다. 도착지점이 가까운 지점부터 나열하여 최대한 많이 담아서 가는 것이 좋다. ( ex: (0,3) 20개 (2,5) 40개 있다 했을 때 (0,3) 20개 + (2,5) 20개를 옮기는 것이랑 (2,5) 40개를 옮.. 2023. 4. 6.
[python] 백준 1911 흙길 보수하기 https://www.acmicpc.net/problem/1911 1911번: 흙길 보수하기 어젯밤 겨울 캠프 장소에서 월드 본원까지 이어지는, 흙으로 된 비밀길 위에 폭우가 내려서 N (1 2023. 4. 5.
[python] 백준 1422 숫자의 신 https://www.acmicpc.net/problem/1422 1422번: 숫자의 신 첫째 줄에 K와 N이 공백을 사이에 두고 주어진다. K와 N은 각각 50보다 작거나 같은 자연수이고, N은 K보다 크거나 같다. 둘째 줄에는 K개의 수가 한 줄에 하나씩 주어진다. 각 수는 1,000,000,000보다 www.acmicpc.net 문제 해결 모든 수는 1번 이상씩 사용 하지만 더 사용하는 숫자는 오직 하나이고 가장 큰 수일 것이다.(이유는 첫번째는 자리수가 크기 때문이고 두번째는 자리수가 같으면 앞에 큰수가 오는 것이 큰수이기 때문에 많이 사용할 수록 좋다.) 따라서 가장 큰 수를 변수로 저장한 다음 n-k 만큼 추가적으로 리스트 안에 저장하면 된다. 문제는 숫자 배열이다. 모든 숫자는 $10^{9}.. 2023. 4. 5.
728x90