Greedy

[문제] https://www.acmicpc.net/problem/15903 15903번: 카드 합체 놀이 첫 번째 줄에 카드의 개수를 나타내는 수 n(2 ≤ n ≤ 1,000)과 카드 합체를 몇 번 하는지를 나타내는 수 m(0 ≤ m ≤ 15×n)이 주어진다. 두 번째 줄에 맨 처음 카드의 상태를 나타내는 n개의 자연수 a1, www.acmicpc.net [풀이] 처음에는 간단하게 sort 함수를 이용해 풀었는데 이는 O(nlogn)으로 우선순위 큐를 이용하면 O(logn)으로 시간복잡도를 줄일 수 있다. 우선순위 큐 사용시, 값을 바꿀 카드 2개를 우선순위 큐에 삽입만 하면 되기 때문에 매번 정렬해야하는 sort 보다 훨씬 효율적인 것이다. 따라서 cards 리스트를 만든 후 heapq 내장 모듈 사..

[문제] https://www.acmicpc.net/problem/9009 9009번: 피보나치 입력 데이터는 표준입력을 사용한다. 입력은 T 개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 테스트 데이터의 수를 나타내는 정수 T 가 주어진다. 각 테스트 데이터에는 하나의 정수 n www.acmicpc.net [풀이] 우선 피보나치 리스트를 만들어 올바른 값을 미리 넣어준다. 문제에 n의 최댓값이 1,000,000,000이라고 했기 때문에 44번 째 피보나치 수열까지만 구하면 된다. 만들 수 있는 숫자 중 최소 개수로 n을 만들기 위해서는 n 이하의 수 중 가장 n과 가까운 수를 써야 한다. 문제에 나온 예시처럼 100을 만들기 위해서는 (3 + 8 + 89) 도 가능하지만 (3 + 8 + 34 ..

[문제] https://www.acmicpc.net/problem/3578 3578번: Holes You may have seen a mechanic typewriter — such devices were widespread just 15 years ago, before computers replaced them. It is a very simple thing. You strike a key on the typewriter keyboard, the corresponding type bar rises, and the metallic letter mo www.acmicpc.net [풀이] 문제에 쓸데없는 설명들이 많은데 요약하자면 0, 4, 6, 9 를 타이핑 할 경우 종이에 구멍이 1개 생기고 8 을 타이..

[문제] https://www.acmicpc.net/problem/10162 10162번: 전자레인지 3개의 시간조절용 버튼 A B C가 달린 전자레인지가 있다. 각 버튼마다 일정한 시간이 지정되어 있어 해당 버튼을 한번 누를 때마다 그 시간이 동작시간에 더해진다. 버튼 A, B, C에 지정된 시간은 www.acmicpc.net [풀이] 그리디 문제! 최종 결과는 신경쓰지 않고 일단 현재 가장 이익이 될 것을 선택한다. 여기서 현재 가장 이익이 될 것 = 거스름돈이 제일 작을 것 시간이 긴 버튼을 누르는 게 이익이 되기 때문에 5분부터 차례대로 답을 찾아간다. [코드] import sys T = int(sys.stdin.readline()) A, B, C = 300, 60, 10 if T % C != 0..

[문제] https://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 [풀이] 문제 조건이 큰 동전은 모두 작은 동전의 배수이기 때문에 이 문제는 그리디 알고리즘으로 풀 수 있다. 만약 800원의 가치를 만들어야 하는데, 500원 400원 100원으로 주어지는 경우는 그리디 알고리즘을 쓰면 안된다. 동전 문제에 그리디 알고리즘을 적용하는 것은 쉽다. 동전의 액면가만 보고 판단하면 되기 때문에 ..

[문제] https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net [풀이] 입력받은 회의 시간들을 정렬할 때 시작시간과 종료시간이 같을 수 있어 lambda를 이용해 시작시간으로 정렬해준 뒤, 종료시간으로 한번 더 정렬해준다. 5 3 5 1 4 8 11 4 4 2 2 # 시작시간을 기준으로 정렬했을 경우 [[1, 4], [2, 2], [3, 5], [4, 4], [8, 11]] # 시작시간 기준 정렬 후 종료시간 기준으로 정렬했을 경우 [[2, 2], [1, 4], [4, 4], [3, 5], [8, 11]] 가능한 회의 개수를 세는 부분은 고민을 많이 했다.. 현재 ..

[문제] https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net [풀이] 처음 각 사람이 돈 인출에 걸리는 시간을 리스트에 넣을 때 sorted() 함수를 이용해 오름차순으로 리스트를 정렬해 저장한다. temp와 res를 0으로 초기화한다. temp에는 for문을 돌 때마다 위 첨부사진의 두 번째 줄 숫자가 저장된다. res는 temp 값을 더한다. (3번째 줄) [코드] import sys if __name__ == '__main__': n = int(sys.stdin.readl..

[문제] https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net [풀이] 수를 최솟값으로 만들기 위해서는 마이너스가 나왔을 때 가장 큰 수를 빼면 된다. 따라서 최초의 - 연산자가 나오기 전까지는 전부 더하고, - 엱산자가 나온 이후에는 전부 빼준다. '55 - 50 + 40 - 10 + 20' 을 입력으로 받았을 때 split() 함수를 통해 expression = sys.stdin.readline().strip().split('-') prin..

[문제] https://www.acmicpc.net/problem/4796 4796번: 캠핑 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, L, P, V를 순서대로 포함하고 있다. 모든 입력 정수는 int범위이다. 마지막 줄에는 0이 3개 주어진다. www.acmicpc.net [풀이] 휴가 v일 중 v//p 값은 캠핑장을 온전히 이용할 수 있는 날이다. 휴가 v일 중 v%p과 l 중 더 작은 일수만큼 캠핑장을 이용할 수 있다. [코드] - 첫 번째 방법 if __name__ == '__main__': case = 0 while True: l, p, v = map(int, input().split()) if l+p+v == 0: break case += 1..