1715번: 카드 정렬하기 (acmicpc.net) 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 문제 코드 from heapq import heappush, heappop hq=[] n=int(input()) for _ in range(n): x=int(input()) heappush(hq, x) #마지막에 합쳐지는수는 어차피 동일 #대신 초반부터 적게 합치고 합쳐야함. ans=0 while(len(hq) !=1): a = heappop(hq) b = heappop(hq) ans += a+b..
Koala - 12기/코딩테스트 준비 스터디
https://www.acmicpc.net/problem/2559 2559번: 수열 첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 www.acmicpc.net 문제 코드 import sys n, k = map(int,sys.stdin.readline().split()) a = list(map(int, sys.stdin.readline().split())) result = list() result.append(sum(a[:k])) for i in range(n - k): result.append(result[i] - a[i] + a[k+i])..
https://www.acmicpc.net/problem/15810 문제 전북대학교 프로그래밍 경진 대회에서는 ACM-ICPC 스타일을 따라 문제를 해결한 팀에게 그 문제에 해당하는 풍선을 달아준다. 풍선을 담당하는 N명의 스태프가 있다. 스태프마다 폐활량이 다르기 때문에 하나의 풍선을 만드는 데 걸리는 시간은 다양하다. 대회가 시작되고 운영진으로부터 M개의 풍선을 만들어 달라는 의뢰가 들어왔다! 각 스태프가 풍선 하나를 만드는 시간(분) Ai를 알고 있을 때, 풍선 M개를 만들기 위해서 최소 몇 분이 걸릴까? 풍선을 만든 후에 문제를 표시할 것이기 때문에 풍선의 종류는 상관이 없다. 모든 스태프는 풍선을 만드는 데에 정확하게 자신이 말한 시간만큼 걸린다. 예를 들어 스태프 A가 풍선 하나를 만드는 데 ..
문제 https://www.acmicpc.net/problem/11441 풀이 주어진 구간의 합 구하기는 누적합을 활용하여 풀 수 있다. 누적합을 구한 뒤, 주어진 구간에 맞춰 일부 구간을 빼주면 된다. 만약 구간이 1부터 시작이 아닌 3~4라면, 1~4에서 1~2를 빼주면 남은 것은 3~4이다. 해당 원리로 주어진 구간에 대해 계산해주면 된다. 코드 N = int(input()) A = [0] + list(map(int, input().split())) M = int(input()) sections = [list(map(int, input().split())) for _ in range(M)] psum = [0]*(N+1) for i in range(1,N+1): psum[i] = psum[i-1]+A..
https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 알고리즘 분류 이분 탐색 매개 변수 탐색 문제 집에서 시간을 보내던 오영식은 박성원의 부름을 받고 급히 달려왔다. 박성원이 캠프 때 쓸 N개의 랜선을 만들어야 하는데 너무 바빠서 영식이에게 도움을 청했다. 이미 오영식은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이다. 박성원은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에..
문제 https://www.acmicpc.net/problem/21921 알고리즘 분류 : 누적합 21921번: 블로그 첫째 줄에 $X$일 동안 가장 많이 들어온 방문자 수를 출력한다. 만약 최대 방문자 수가 0명이라면 SAD를 출력한다. 만약 최대 방문자 수가 0명이 아닌 경우 둘째 줄에 기간이 몇 개 있는지 출력한다 www.acmicpc.net 코드 #include #include using namespace std; //21921번 블로그 //맨처음부터 x까지수를 배열에 넣은후 반복문을 통해 앞에만 넣고 뒤에를 빼면서 탐색 int main() { int n = 0; int x = 0; cin >> n >> x; vector arr; vector srch; int a = 0; for (int i = ..
문제 풀이 R*C 크기의 사진에 대한 밝기가 주어지면, 사진의 일부분에 해당하는 밝기 평균을 구하는 문제이다. 2차원 배열의 누적합을 구하고, 사진의 일부분의 가로*세로로 나누어주면 된다. 코드 #include using namespace std; int R, C, Q; int picture[1001][1001]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> R >> C >> Q; for (int i = 1; i picture[i][j]; picture[i][j] += picture[i - 1][j] + picture[i][j - 1] - picture[i - 1][j - 1]; } } int r1, c1, r2, ..
풀이 실패율은 (스테이지에 도달하였으나 아직 클리어하지 못한 플레이어 수) / (스테이지에 도달한 플레이어수) 에 해당한다. 각 플레이어들에 대하여 각자 있는 곳들을 ✔️로 표시하고, 그 전 단계까지는 클리어한 것이므로 o로 표시해 나열해보면 아래와 같이 플레이어는 각 단계에 있어서의 ✔️/(✔️+o)에 해당하는 것을 알 수 있다. 1 o ✔️ o o o o o o ✔️/(✔️+o) 2 ✔️ x ✔️ o ✔️ o o o 3 x x x o x o ✔️ ✔️ 4 x x x o x ✔️ x x 5 x x x o x x x x 코드 def solution(N, stages): answer = [] List1 = [0 for _ in range(N+2)] List2 = [0 for _ in range(N+2)] ..
https://www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 문제 문제해석 투포인터를 활용하여 0에 가장 가까운 혼합 용액을 만드는 두 용액을 찾는 문제이다 코드 N = int(input()) check = list(map(int, input().split())) left, right = 0, N - 1 Min = abs(check[left] + check[right]) result = [check[left], check[right]] while (l..
https://www.acmicpc.net/problem/1966 문제 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 쌓여서 FIFO - First In First Out - 에 따라 인쇄가 되게 된다. 하지만 상근이는 새로운 프린터기 내부 소프트웨어를 개발하였는데, 이 프린터기는 다음과 같은 조건에 따라 인쇄를 하게 된다. 현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 확인한다. 나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 Queue의 가장 뒤에 재배치 한다. 그렇지 않다면 바로 인쇄를 한다. 예를 들..
문제 https://www.acmicpc.net/problem/1940 1940번: 주몽 첫째 줄에는 재료의 개수 N(1 ≤ N ≤ 15,000)이 주어진다. 그리고 두 번째 줄에는 갑옷을 만드는데 필요한 수 M(1 ≤ M ≤ 10,000,000) 주어진다. 그리고 마지막으로 셋째 줄에는 N개의 재료들이 가진 고 www.acmicpc.net 풀이 갑옷을 만들기 위해 두 개의 재료가 필요하므로 투 포인터를 이용하여 구현할 수 있다. 먼저 입력받은 고유한 번호들을 정렬하고, 양 끝(l, r)에서 시작하여 두 수의 합이 m이 되는지 확인하면 된다. 합이 m이라면, 왼쪽(l)을 오른쪽으로 한 칸 옮기고 오른쪽(r)은 왼쪽으로 한 칸 옮긴다. 합이 m보다 작다면, 왼쪽을 오른쪽으로 한 칸 옮긴다. (l += 1)..
문제 https://www.acmicpc.net/problem/1644 풀이 먼저 소수를 찾는 방법은 에라토스테네스의 체 방법으로 찾을 수 있다. 2부터 자신이 현재까지 나눠지지 않아 True(소수)라면, 해당 수를 소수 리스트에 넣고 그의 배수를 False(소수가 아님)으로 바꿔준다. 이후 소수들에 대해 투포인터를 활용해 연속된 수의 합을 구해본다. 연속된 수의 합이 원하는 수라면 count를 하나씩 늘려 값을 찾는다. 코드 N = int(input()) eratos = [False, False] + [True]*(N-1) primes = [] for i in range(2,N+1): if eratos[i]: primes.append(i) for j in range(2*i, N+1, i): eratos..
