본문 바로가기
728x90

정렬34

[python] 백준 2258 정육점 https://www.acmicpc.net/problem/2258 2258번: 정육점 첫째 줄에 두 정수 N(1 ≤ N ≤ 100,000), M(1 ≤ M ≤ 2,147,483,647)이 주어진다. N은 덩어리의 개수를 의미하고, M은 은혜가 필요한 고기의 양이다. 다음 N개의 줄에는 각 고기 덩어리의 무게와 가격을 나 www.acmicpc.net 문제 해결 특이한 것이 어떤 고기의 가격보다 싼 고기들이 공짜라는 점이다. 그러므로 가격이 싼 것부더 정렬을 하여 for 문을 통해 가격을 정한 다음 그 이전의 고기의 무게들을 더해 원하는 고기량보다 큰 것들을 종합하여 가장 작은 가격이 정답이 된다. 가격 오름차순으로 정렬했기 때문에 가능한 답이 나오면 그것이 정답이라고 생각할 수 있지만 이전과 동일한 가격이.. 2023. 4. 13.
[python] 백준 2141 우체국 https://www.acmicpc.net/problem/2141 2141번: 우체국 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 X[1], A[1], X[2], A[2], …, X[N], A[N]이 주어진다. 범위는 |X[i]| ≤ 1,000,000,000, 1 ≤ A[i] ≤ 1,000,000,000 이며 모든 입력은 정수이다. www.acmicpc.net 문제 해결 $ L_{1} $ 공간에서 $ \sum_{i=1}^{n} |x_{i}-a| \times b $ 의 최솟값은 표본의 중앙값이 위치한 값이라는 것을 이용하는 문제이다. https://math.stackexchange.com/questions/4410205/minimum-value-of-sum-of-absolu.. 2023. 4. 9.
[python] 백준 5052 전화번호 목록 https://www.acmicpc.net/problem/5052 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net 문제 해결 최대한 비교를 적게 하기 위해 문자열을 올림차순으로 정렬해서 이전 것이 다음 원소 안에 포함되는 것이 있는지 확인하면 된다는 것을 쉽게 알 수 있다. CODE t = int(input()) for _ in range(t): n = int(input()) result = [] for i in range(n): x = str(input().rstrip()) resul.. 2023. 4. 9.
[python] 백준 2457 공주님의 정원 https://www.acmicpc.net/problem/2457 2457번: 공주님의 정원 첫째 줄에는 꽃들의 총 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 각 꽃이 피는 날짜와 지는 날짜가 주어진다. 하나의 날짜는 월과 일을 나타내는 두 숫자로 표현된다. 예를 들어서, www.acmicpc.net 문제해결 월/일 을 표현할때 '월*100+일'로 표현하여 비교할 수 있다. 투포인터를 이용해 문제를 해결할 수 있다. 3월 1일~11월 30일 꽃이 매일 한 개 이상 피어있어야 하므로 301~1130을 포함하는 범위를 만들면 된다. start = 301, end = 0으로 시작하여 start범위이하부터 시작하여 지는 범위가 1130 보다 커지면 가능한 경우가 있고 그렇지 않으면.. 2023. 4. 8.
728x90