본문 바로가기
728x90

그리디41

[python] 백준 2831 댄스 파티 https://www.acmicpc.net/problem/2831 2831번: 댄스 파티 남자 N명과 여자 N명이 상근이가 주최한 댄스 파티에 왔다. 상근이는 모든 사람의 키를 알고있다. 각 남자는 모두 여자와 춤을 출 수 있고, 여자는 남자와 춤을 출 수 있다. 모든 사람은 많아야 한 www.acmicpc.net 문제 해결 음수-양수, 양수-음수만 짝이 가능하다. 음수쪽 절대값이 더 커야한다. sort()를 통해 수를 배열하고 음수인 부분이 더 클 경우에 짝을 만들어준다. 남자는 가장 작은수부터, 여자는 가장 큰 수부터 시작해서 짝을 맞춰본다.(절대값이 큰것끼리 짝을 맞춰야 더 많이 짝을 만들 수 있다.) CODE n = int(input()) M = list(map(int, input().split(.. 2023. 5. 6.
[python] 백준 18185 라면 사기 (small) https://www.acmicpc.net/problem/18185 18185번: 라면 사기 (Small) 라면매니아 교준이네 집 주변에는 N개의 라면 공장이 있다. 각 공장은 1번부터 N번까지 차례대로 번호가 부여되어 있다. 교준이는 i번 공장에서 정확하게 Ai개의 라면을 구매하고자 한다(1 ≤ i www.acmicpc.net 문제 해결 단순히 3개를 많이 사고 2개 1개를 사면 좋을거라 생각하기 쉽다. 하지만 j, j+1, j+2 공장 라면이 만약 3 5 2 로 있다고 생각해보자. 3개를 먼저 사면 7*2 + 5*1 + 3*2 = 25일 것이다. j+1,j+2공장 차이만큼 j와 j+1공장에서 라면을 먼저 사도 5*3 + 5*2 = 25이다. 하지만 j+3 고장에 만약 2개가 있다면? 3개를 먼저 사는.. 2023. 4. 29.
[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] 백준 1727 커플 만들기 https://www.acmicpc.net/problem/1727 1727번: 커플 만들기 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 줄에는 n명의 남자들의 성격이 주어진다. 그 다음 줄에는 m명의 여자들의 성격이 주어진다. 성격은 1,000,000이하의 자연수이다. www.acmicpc.net 문제 해결 커플 만드는 문제 최근 코딩테스트에서 나오는 문제 유형이다.(사실 이것보다 더 어렵다.ㅠㅠ) 시간복잡도 신경쓰면서 커플을 연결하는 것이 쉽지 않다. 구하고자 하는 것은 성격의 차이의 합이 최소가 되는 것이다. 따라서 누적합을 통해 답을 도출하도록 한다. sort를 통해 성격을 수치화한 것을 오름차순으로 만든 다음 남자 0번과 가장 맞는 여자 j(0 2023. 4. 24.
728x90