Algorithm/Greedy27 [파이썬] 백준 2109 : 순회강연 (골드3) [파이썬] 백준 2109 : 순회강연 (골드3) 2109번: 순회강연 한 저명한 학자에게 n(0 ≤ n ≤ 10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면 p(1 ≤ p ≤ 10,000)만큼의 강연료를 지불하겠다고 알려왔다. www.acmicpc.net 문제 풀이 0. 방향성 생각 역순으로 접근하는 그리디 1. 입력 from collections import defaultdict as dd import heapq as hq import sys input = lambda : sys.stdin.readline().rstrip() table = dd(list) for _ in range(int(input())): p,d = map(i.. 2023. 12. 12. [파이썬] 백준 2258 : 정육점 (골드4) [파이썬] 백준 2258 : 정육점 (골드4) 2258번: 정육점 첫째 줄에 두 정수 N(1 ≤ N ≤ 100,000), M(1 ≤ M ≤ 2,147,483,647)이 주어진다. N은 덩어리의 개수를 의미하고, M은 은혜가 필요한 고기의 양이다. 다음 N개의 줄에는 각 고기 덩어리의 무게와 가격을 나 www.acmicpc.net 문제 풀이 0. 방향성 생각 특정 가격 고기를 사면 싼 고기를 모두 고를 수 있다. table[가격] = [무게1, 무게2, ...] 이런식으로 나타내서 무게 역순으로 정렬하기. 긴 배열에서 가격 연산을 줄이기 위해서 누적 합 사용. 1. 입력 from collections import defaultdict as dd import sys input = lambda : sys.st.. 2023. 12. 10. [파이썬] 백준 1781 : 컵라면 (골드2) [파이썬] 백준 1781 : 컵라면 (골드2) 1781번: 컵라면 상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라 www.acmicpc.net 문제 풀이 0. 방향성 생각 현재 최선의 선택(점수 많이주는거)이 항상 최적의 결과를 불러오지 않는다. 데드라인을 고려하면서 컵라면을 선택해야함 순차적으로 골랐을 경우, 저장한 자료구조에서 데드라인을 넘긴 경우를 모두 제거해줘야함 2023. 11. 30. [파이썬] 백준 28709 : 와일드카드 괄호 문자열 (골드1) [파이썬] 백준 28709 : 와일드카드 괄호 문자열 (골드1) 28709번: 와일드카드 괄호 문자열 각 테스트케이스마다 한 줄에 하나씩, ‘?’ 문자를 ‘(’이나 ‘)’로, ‘*’ 문자를 ‘(’, ‘)’로 이루어진 길이가 $0$ 이상인 원하는 문자열로 대체하여 $S$를 올바른 괄호 문자열로 만들 수 www.acmicpc.net 문제 풀이 0. 방향성 생각 *이 있는 케이스와 없는 케이스로 나눈다. 왜 와이 - > 입력 문자열 S를 split('*')을 통해 나누면 항상 다음의 케이스로 나누어진다. S = *A꼴 -> string = ['',A] : 왼쪽에서 '('를 무한정 공급 가능하다. 뒤에서부터 순회해서 (개수가 ?)개수랑 일치시킨다. S = A*꼴 -> string = [A,''] : 오른쪽에서 .. 2023. 10. 22. 이전 1 2 3 4 5 6 7 다음
