본문 바로가기
728x90

그리디41

[python] 백준 1781 컵라면 https://www.acmicpc.net/problem/1781 1781번: 컵라면 상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라 www.acmicpc.net 문제 해결 데드라인을 생각하면서 컵라면 수가 큰 것을 스택 안에 넣는 문제 스택 안의 원소의 개수를 데드라인이라고 생각하면 된다. 그러면 스택 안에 원소를 데드라인이 빠른 것부터 처리를 하며 만약 컵라면은 많이가져갈 수 있는데 데드라인이 걸리면 그 전에 작은 컵라면수를 빼고 넣으면 된다. CODE import heapq n = int(input()) table = [] for _ in range(n): d.. 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.
[python] 백준 9576 책 나눠주기 https://www.acmicpc.net/problem/9576 9576번: 책 나눠주기 백준이는 방 청소를 하면서 필요 없는 전공 서적을 사람들에게 나눠주려고 한다. 나눠줄 책을 모아보니 총 N권이었다. 책이 너무 많기 때문에 백준이는 책을 구분하기 위해 각각 1부터 N까지의 www.acmicpc.net 문제 해결 어떤 범위를 가진 학생한테 먼저 책을 줄지 생각을 해야한다. 범위길이가 작은 사람부터 해결하는 것이 좋다.(가능한 경우의 수가 적으므로) 그러면 right upperbound는 작을수록, left lowerbound는 클 수록 먼저 해결하는 것이 좋다. CODE from collections import deque for _ in range(int(input())): n, m = map(i.. 2023. 4. 5.
[python] 백준 1826 연료 채우기 https://www.acmicpc.net/problem/1826 1826번: 연료 채우기 첫째 줄에 주유소의 개수 N(1 ≤ N ≤ 10,000)가 주어지고 두 번째 줄부터 N+1번째 줄 까지 주유소의 정보가 주어진다. 주유소의 정보는 두개의 정수 a,b로 이루어 져 있는데 a(1 ≤ a ≤ 1,000,000)는 성경 www.acmicpc.net 문제 해결 처음에 재귀(recursion)를 이용해 풀려고 했다. 하지만 모든 경우의 수를 다 찾아보는 것은 불필요하고 recursionError가 뜨게 되었다. 힙을 이용해 문제를 풀 수 있다고 하는데 어떻게 풀어야할지 몰랐다. 다른 분들의 풀이를 참고하여 풀 수 있게 되었다. 바로 계속 지나간다고 가정하고 만약 기름이 부족하게 되면 기름을 채우고 나서~채우.. 2023. 4. 4.
728x90