탐욕법3 [백준] 2217 - 로프 (Python) 문제 출처 : www.acmicpc.net/problem/2217 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net 문제 풀이 : 최대무게를 걸어야하고 , "몇 개"의 로프만 골라서 사용할 수 있다. 로프를 여러개 사용하는게 무게가 줄어들어서 좋을까? 라는 생각이 들 수 있지만 주의해야하는 것은 로프마다 견딜 수 있는 무게가 다르다는 점이다. 이런 점을 보았을때 로프를 내림차순으로 정렬 시킨후 모든 로프에 대해서 무게를 늘려가며 최대값을 갱신해주면된다. 제일 무거운 무게를 지탱할 수 있는 로프 순서대로.. 2021. 3. 30. [백준] 1931 - 회의실 배정 (Python) 문제 출처 : www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 문제 풀이 : 이 문제에서 살펴보아야할 점은 끝나는 시간과 시작하는 시간이 같다면 바로 시작할 수 있다는 점이다. 때문에 주어진 회의시간을 끝나는 시간, 시작 시간으로 정렬한 뒤에 가장 먼저 시작해서 짧은 거 순으로 넣으면 그것이 전체에서도 최대가 될 것이라고 생각한다. 앞쪽에서 시간을 조금 잡아 먹을 수록 뒤에서 고려해 줄 수 있는 것이 많기 떄문이다. 때문이 이것은 그리디로 풀 수 있다. n = int(input()) meeting = [] for i in range(n): start, end = map(in.. 2021. 3. 27. [백준] 11047 - 동전 0 (Python) 문제 출처: www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 문제 풀이: 이 문제가 DP가 아니고 Greedy 문제라는 것을 알 수 있는게 문제에서 보면 주어지는 코인이 서로 배수 관계를 가지고 있으며 정렬되어 주어진다는걸 알 수 있다. 사실 배수관계만 유지되면 정렬은 우리가 해주어도 된다. 배수관계가 중요한 포인트인 이유는 배수관계를 유지함으로써 local optimal solution을 구하.. 2021. 3. 26. 이전 1 다음 반응형
