본문 바로가기
728x90

정렬34

[python] 백준 10800 컬러볼 https://www.acmicpc.net/problem/10800 10800번: 컬러볼 첫 줄에는 공의 개수를 나타내는 자연수 N이 주어진다(1 ≤ N ≤ 200,000). 다음 N개의 줄 중 i번째 줄에는 i번째 공의 색을 나타내는 자연수 Ci와 그 크기를 나타내는 자연수 Si가 주어진다(1 ≤ Ci ≤ N www.acmicpc.net 문제 해결 우선 기준크기보다 크면 계산할 필요가 없으므로 sort()를 이용하여 공에 대한 정보를 공의 크기 오름차순으로 나타낸다. 크기가 기준크기보다 작아도 색이 같으면 계산에서 제외되므로 색깔별로 크기합에 대한 고려를 해야한다. 위의 생각을 통해 sort()를 한 후 for문으로 하나씩 기준을 잡는다. 이때 공의 크기가 작은 것부터 기준을 잡기 때문에 인덱스i 보다.. 2023. 5. 4.
[python] 백준 4716 풍선 https://www.acmicpc.net/problem/4716 4716번: 풍선 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 팀의 수 N(1 ≤ N ≤ 1,000)과 방 A와 B에 보관되어있는 풍선의 수 A, B가 주어진다. (0 ≤ A, B ≤ 10,000) 다음 N개 www.acmicpc.net 문제 해결 거리를 비교해서 A아니면 B를 선택하는 문제로 보면 된다. A와 B와 거리가 같으면 풍선 남는 쪽으로 가면 되는데 풍선이 모자랄 일이 없으므로 그냥 계산하면 된다. CODE while True: n, a, b = map(int, input().split()) if n==0 and a==0 and b==0:break X = [list(map(int, input.. 2023. 4. 28.
[python] 백준 7453 합이 0인 네 정수 https://www.acmicpc.net/problem/7453 7453번: 합이 0인 네 정수 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다. www.acmicpc.net 문제 해결 먼저 n행이면 배열의 크기가 n이라는 것이고 열은 각각 A,B,C,D를 나타낸다는 것을 알아야한다. A,B,C,D를 각각 원소를 찾기에는 (O($n^{4}$))의 시간복잡도가 나오기 때문에 가급적 줄여야한다. 따라서 AB원소의 합을 ab에 CD원소의 합을 cd에 넣어서 줄일려고 하였다.(O($n^{2}$)) 그리고 원소를 각각 오름차순으로 배열을 하고 ab는 인덱스0부.. 2023. 4. 25.
[python] 백준 2473 세 용액 https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 문제 해결 전형적인 이분탐색 문제 (세 원소의 합이 C(상수) 일때 세 원소를 구하는 문제) 가장 작은 수를 고정시키고 나머지 두 수를 이분탐색으로 구하는 문제 그런데 python3에서는 시간초과가 난다...ㅜㅜ(pypy3에서는 잘 풀림) 근데 다른 분들도 이렇게 많이 푼듯? CODE import sys input = sys.stdin.readline INF =sys.maxs.. 2023. 4. 24.
728x90