목록Greedy (6)
Koo's.Co
[Python] 9440 - 숫자 더하기 9440번: 숫자 더하기 강민이가 초등학교 3학년일 때, 담임선생님이 이런 문제를 냈었다. 숫자 1, 2, 7, 8, 9 를 사용해서 만든 두 숫자를 더했을 때, 나올 수 있는 가장 작은 수는 무엇일까요? 강민이 koosco.tistory.com [Python] 2864 - 5와 6의 차이 2864번: 5와 6의 차이 첫째 줄에 두 정수 A와 B가 주어진다. (1 koosco.tistory.com [Python] 11501 - 주식 11501번: 주식 입력의 첫 줄에는 테스트케이스 수를 나타내는 자연수 T가 주어진다. 각 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘째 줄에는 날 별 koosco.tis..
25045번: 비즈마켓 비즈마켓은 "고객 기업 운영의 효율화에 기여하며, 그 구성원의 복지 만세를 추구한다." 라는 기조 아래 기업을 주 대상으로 복지몰 사업, 기업 판촉 및 사은품 사업, 산업재 유통 사업을 하는 온 www.acmicpc.net 풀이 상품 만족도와 비용의 차이를 정렬하여 비교해주었습니다. 두 리스트에 대한 각각의 iterable 변수를 설정한 후 상품 만족도보다 비용이 크다면 다음 상품 만족도와 비교하는 방식을 사용했습니다. import sys read = sys.stdin.readline n, m = map(int, read().split()) a = sorted(list(map(int, read().split())), reverse=True) b = sorted(list(map(in..
11501번: 주식 입력의 첫 줄에는 테스트케이스 수를 나타내는 자연수 T가 주어진다. 각 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘째 줄에는 날 별 주가를 나타 www.acmicpc.net 풀이 1) 처음 풀이할 때는 앞에서부터 최댓값을 구한 후 최댓값까지의 차를 모두 더하는 것을 반복하는 방법을 생각했다. 시간복잡도가 O(N^2)으로 시간 초과가 나와서 다른 방법을 찾아보게 되었다. import sys read = sys.stdin.readline for T in range(int(read())): n, stocks = int(read()), list(map(int, read().split())) res = 0 while len(sto..
[Python] 11399 - ATM 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 풀이 인출할 때 걸리는 사람이 먼저 koosco.tistory.com [Python] 2777 - 숫자놀이 2777번: 숫자 놀이 첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 양의 정수 N이 주어진다. (1 10: print(-1) flag = True break if flag: continue while idx < len(tmp): if n koosco.tistory.com [Python] 2785..
13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 풀이 처음 주유소의 기름 가격을 최소로 설정한다. 이후에 나오는 주유소의 기름 가격이 현재 주유소의 기름 가격보다 크다면 현재 기름 가격을 유지한다. 이후에 나오는 주유소의 기름 가격이 현재 주유소의 기름 가격보다 작다면 해당하는 주유소까지만 현재 주유소 가격으로 간 후, 해당 주유소부터는 더 기름값이 싼 기름을 주유한다. import sys input = sys.stdin.readline n = int(input()) road_costs = lis..
2785번: 체인 희원이는 그의 다락방에서 N개의 체인을 찾았다. 각각의 체인은 몇 개의 고리로 연결되어 있는데, 각각의 고리는 최대 두 개의 인접한 고리를 가질 수 있다. 각각의 고리는 열고 닫을 수 있다. 그 www.acmicpc.net 풀이 입력받은 체인을 정렬한 후 가장 작은 체인부터 풀면서 큰 체인을 연결시켜준다. 체인을 푼 후에 연결할 때마다 전체 체인의 개수가 하나씩 줄어들기 때문에 전체 체인 개수가 1이 될 동안 반복한다. 체인 하나를 다 쓴 경우 체인 하나가 없어지는 것이기 때문에 이 경우에도 전체 체인의 개수를 1감소시킨다. import sys read = sys.stdin.readline n = int(read()) chains = sorted(list(map(int, read().s..