[유형]DP [문제링크]https://www.acmicpc.net/problem/2293 [요약]n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다.사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다. [문제풀이]for coin in coins: 이전에 사용한 동전은 쓸 수 없다.dp[4] (1,2원으로 4를 만드는 경우의 수) = dp[4] (원래 1원으로만 4를 만드는 경우의 수) + dp[4-2] (1,2원으로 2를 만드는 경우의 수)import sysfrom collections import Counterdef input(): ..

[유형]그리디  [문제링크]https://www.acmicpc.net/problem/11047 [요약]준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오. [문제풀이]coins의 리스트 안에서 M으로 나눌 수 있는 가장 큰 수를 찾는다.몫은 answer에 더해주고 나머지는 M에 부여한다.import sysfrom collections import Counterdef input(): return sys.stdin.readline().rstrip()N, M = map(int, input().split())coins = []for _ in range(N)..

[유형]이분탐색 [문제링크]https://www.acmicpc.net/problem/3079 [요약]첫째 줄에 상근이와 친구들이 심사를 마치는데 걸리는 시간의 최솟값을 출력한다. [문제풀이]end : M명이 입국 심사를 하는데 걸리는 최대 시간. T_K의 최댓값이 10^9이므로, 10^9*M으로 초기화한다.mid: 임의의 입국 심사하는데 걸리는 시간.cnt: mid 동안 입국심사할 수 있는 사람의 수cnt>=M: 상근이와 친구들의 수보다 입국심사할 수 있는 사람의 수가 많다는 것으로, 임의의 입국심사하는데 걸리는 시간을 줄인다.반대의 경우, 임의의 입국심사하는데 걸리는 시간을 늘린다.import sysfrom collections import Counterdef input(): return sys...

[유형]이분탐색 [문제링크]https://www.acmicpc.net/problem/2805 [요약]첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다.적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 출력한다. [문제풀이]mid: 임의의 절단기 높이cnt: 집에 가져갈 나무의 길이의 합cnt >= M: 집에 가져가려고 했던 길이보다 긴 경우, 절단기의 높이를 높이고반대의 경우에는 절단기의 높이를 낮춘다.import sysfrom collections import Counterdef input(): return sys.stdin.readline().rstrip()N, M = map(int, input().split())trees ..

[유형]이분탐색  [문제링크]https://www.acmicpc.net/problem/10815 [요약]숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오. [문제풀이]N_list를 리스트로 사용하면 시간초과가 발생한다.N_list를 dictionary나 Counter를 사용하면 시간 초과가 발생하지 않고 문제를 해결할 수 있다.import sysfrom collections import Counterdef input(): return sys.stdin.readline().rstrip()N = int(input())N_list = Counter(..

[유형]이분탐색 [문제링크]https://www.acmicpc.net/problem/1789 [요약]서로 다른 N개의 자연수의 합이 S라고 한다. S를 알 때, 자연수 N의 최댓값은 얼마일까? [문제풀이]1부터 N까지의 합 = N(N+1)//2import sysfrom collections import defaultdictdef input(): return sys.stdin.readline().rstrip()s = int(input())cnt = 1while cnt*(cnt+1)//2