Coding Test/Geedy

1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net """ 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 10장, 20장, 40장의 묶음 10+20, 40 => 30, 40 : (10 + 20) + (30 + 40) = 100번의 비교 10+40, 20 => 50, 20 : (10 + 40) + (50 + 20) = 120번의 비교 N개의 숫자 카드 묶음의 각각의 크기가 주어질 때, 최..

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 """ 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다. 동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값 출력 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) """ import sys input=sys.stdin.readline n,m=map(int,input().split()) a=[] for _..

문제 N(1~1,000)개의 동전으로 만들 수 없는 양의 정수 금액 중 최솟값 출력 5 3 2 1 1 9 분석 동전을 화폐 단위 기준으로 정렬한 뒤에, 화폐 단위가 작은 동전부터 하나씩 확인하면서 target 변수를 업데이트 풀이 n=int(input()) a=list(map(int, input())) a.sort() target=1 for i in a: # 만들 수 없는 금액을 찾았을 때 반복종료 if target

5585번: 거스름돈 타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사 www.acmicpc.net 분석 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문에 그리디 알고리즘으로 해결 가능 풀이 """ 500엔, 100엔, 50엔, 10엔, 5엔, 1엔짜리 동전이 무수히 많은 경우 1000엔 지폐를 한장 냈을 때, 받을 잔돈에 포함된 잔돈의 개수 지불할 돈 입력 """ m=int(input()) c=[500, 100, 50, 10, 5, 1] n=1000-m cnt=0..

문제 1부터 n까지의 수를 한 번씩만 사용하여 이루어진 수열이 있을 때, 1부터 n까지 각각의 수 앞 에 놓여 있는 자신보다 큰 수들의 개수를 수열로 표현한 것을 역수열이라 한다. 4 8 6 2 5 1 3 7의 역수열 : 5 3 4 0 2 1 1 0 1보다 큰 수는 4, 8, 6, 2, 5. 이렇게 5개이고, 2보다 큰 수는 4, 8, 6. 이렇게 3개, 3보다 큰 수는 4, 8, 6, 5 이렇게 4개.... n과 1부터 n까지의 수를 사용하여 이루어진 수열의 역수열이 주어졌을 때, 원래의 수열을 출력 첫 번째 줄에 자연수 N(3

문제 1부터 N까지의 모든 자연수로 구성된 길이 N의 수열이 주어집니다. 이 수열의 왼쪽 맨 끝 숫자 또는 오른쪽 맨 끝 숫자 중 하나를 가져와 나열하여 가장 긴 증가수열을 만듭니다. 이때 수열에서 가져온 숫자(왼쪽 맨 끝 또는 오른쪽 맨 끝)는 그 수열에서 제거됩니다. 예를 들어 2 4 5 1 3 이 주어지면 만들 수 있는 가장 긴 증가수열의 길이는 4입니다. 맨 처음 왼쪽 끝에서 2를 가져오고, 그 다음 오른쪽 끝에서 3을 가져오고, 왼쪽 끝에서 4, 왼쪽끝에서 5를 가져와 2 3 4 5 증가수열을 만들 수 있습니다. 첫째 줄에 자연수 N(3