Coding Test/Geedy

[1026] 보물

1026번: 보물 첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거 www.acmicpc.net 분석 A 배열 가장 큰 값 * B 배열 가장 작은 값으로 정렬하여 더하기 B에 있는 수 재배열 불가하지만 최솟값 출력이므로 무방 풀이 """ 길이가 N인 정수 배열 A와 B가 있다. 다음과 같이 함수 S를 정의하자. S = A[0]×B[0] + ... + A[N-1]×B[N-1] S의 값을 가장 작게 만들기 위해 A의 수를 재배열하자. 단, B에 있는 수는 재배열하면 안된다. S의 최솟값을 출력 5 1 1 1 6 0 2 7 8 3 1 """ import ..

[1744] 수 묶기 ( 수를 묶어서 최댓값 만들기, 우선순위 큐)

1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 분석 양수 : 가능한 큰 수들끼리 묶음 음수: 음수끼리 곱해서 양수로 더함 0 : 음수가 남는경우 0을 곱함 1 : 다 더함 풀이 import sys input=sys.stdin.readline from queue import PriorityQueue pq = PriorityQueue() # 양수처리 mq = PriorityQueue() # 음수처리 one=0 zero=0 n=int(input()) for _ in range(n): data=int(input(..

[1715] 카드 정렬하기 (우선순위 큐)

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 (동전개수의 최솟값 구하기)

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] 거스름돈

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

침몰하는 타이타닉 (deque)

문제 유람선에는 N명의 승객이 타고 있습니다. 구명보트를 타고 탈출해야 하는데 타이타닉에 있는 구명보트는 2명 이하로만 탈 수 있으며, 보트 한 개에 탈 수 있는 총 무게도 M kg 이하로 제한되어 있습니다. N명의 승객 몸무게가 주어졌을 때 승객 모두가 탈출하기 위한 구명보트의 최소개수를 출력 첫째 줄에 자연수 N(5

창고정리

문제 창고의 가로 길이와 각 열의 상자 높이가 주어집니다. 만약 가로의 길이가 7이라면 1열은 높이가 6으로 6개의 상자가 쌓여 있고, 2열은 3개의 상자, 3열은 9개의 상자가 쌓여 있 으며 높이는 9라고 읽는다. 창고 높이 조정은 가장 높은 곳에 상자를 가장 낮은 곳으로 이동하는 것을 말한다. 가장 높은 곳이나 가장 낮은 곳이 여러곳이면 그 중 아무거나 선택하면 된다. 위에 그림을 1회 높이 조정을 하면 다음과 같아진다. m회의 높이 조정을 한 후 가장 높은 곳 과 가장 낮은 곳의 차이를 출력 10 69 42 68 76 40 87 14 65 76 81 50 풀이 l=int(input()) a=list(map(int, input().split())) m=int(input()) a.sort() for i..