joseph0528 코딩 블로그

이 문제는 입력된 9개의 숫자 중 합이 100이 되는 7개의 숫자를 고르면 되는 문제인데, 이를 다시 생각해보면 나머지 두명의 값을 제외했을 때 100이 되는 경우를 고르는 문제로 바꿀 수 있다. 이 경우 2중 반복문을 통해 두 수의 합을 전체 합에서 뺀 값이 100이 된다면 해당 두값을 제외한 나머지 값들을 출력해주면 된다. 문제가 스페셜 저지이므로 답이 여러개가 될 수 있기 때문에 여러가지 답이 나올 수 있지만 맨처음에 나온 값을 출력해주면 된다. n=9 l=[int(input())for i in range(n)] l.sort() s=sum(l) nanjaeng=[0,0] for i in range(n): for g in range(n): if i!=g and s-100==l[i]+l[g]: nanj..

(한별이가 나오는 몇 안 되는 희귀한 문제이다.) 이 문제는 한가지 관찰만 하면 쉽게 풀 수 있다. 그 관찰은 바로 많아도 3개의 용기만 있으면 꽉 찬 용기를 만들 수 있다는 것이다. 만약 a 용기에 0ml가 있고 b 용기에 1ml가 있고 총용량이 10ml 일 때 a와 b를 합치면 1+5=6ml가 된다. 그리고 c 용기에 2ml가 있다고 하고 앞에서 구한 6ml 용기와 c를 더하면 6+2+5로 10ml를 넘어간다. 이걸 하나의 식으로 나열하면 a+b+c+10/2+10/2 가 된다. 즉 a, b, c 모두 0ml 이어도 10/2 가 두 번 더해져 10으로 꽉 찬 용기가 되기 때문에 최대 3개의 용기만 있으면 꽉 찬 용기를 만들 수 있는 것이다. 맨 처음에 정렬을 해준 뒤 C[i]가 X와 같다면 혼자서도 꽉..

https://www.acmicpc.net/problem/17668 17668번: 시험 $N$명의 학생이 수학 부문과 정보 부문이 있는 시험을 쳤다. $i$번째 ($1 \le i \le N$) 학생은 수학에서는 $S_i$점을, 정보에서는 $T_i$점을 받았다. T교수와 I교수는 각 학생이 시험을 통과할지 말지를, www.acmicpc.net 이 문제 세그 스위핑이라는 방법이 있다고는 하지만 그 방법이 아닌 2차원 머지 소트 트리를 박는 방법으로 했다. 방법은 생각보다 간단한다. A에서 이분 탐색을 해 입력값 이상인 값들의 위치에 있는 B에서 이분 탐색을 또 하고 거기서도 이상인 값들의 위치 중 합이 입력값 이상인 값을 찾아주면 된다. 말만 간단한거 같지만 이 방법을 그대로 머지 소트 트리에 해주면 된다...

https://www.acmicpc.net/problem/17274 17274번: 카드 공장 (Large) 진서는 CTP 카드 공장의 노동자이다. 공장에는 N개의 카드가 있으며 각 카드에는 앞면과 뒷면에 숫자가 쓰여있다. 공장장 노진의 명령에 따라서 진서는 카드를 뒤집어야 한다. 명령은 M번 내려지 www.acmicpc.net 생각보다 어려웠던 문제였다 구현 자체는 오래 걸리지는 않았는데 생각하는데 오래 걸린 거 같다. 처음엔 앞면 기준 정렬된 순서로 앞면 머지 소트 트리와 뒷면 머지 소트 트리 이렇게 두 개의 트리를 만들고 구간을 다른 트리와 바꾸고 합치는 그런 방법을 생각했었는데 그럴 경우 한번 쿼리당 NlogN이라는 시복이 나와서 MNlogN으로 터지게 된다. 문제를 잘 생각해보면 M개의 입력 중에..

solved.ac 티어 : 골 4 https://www.acmicpc.net/problem/8983 8983번: 사냥꾼 입력의 첫 줄에는 사대의 수 M (1 ≤ M ≤ 100,000), 동물의 수 N (1 ≤ N ≤ 100,000), 사정거리 L (1 ≤ L ≤ 1,000,000,000)이 빈칸을 사이에 두고 주어진다. 두 번째 줄에는 사대의 위치를 나타내는 M개의 x-좌 www.acmicpc.net 오랜만에 시험 끝나고 돌아왔다 당연히 시험은 망했고 오랜만에 와서 풀이를 쓸려고 한다 이 문제는 KOI 2013 중등, 고등 1번 문제이다 이 문제는 자명 풀이가 이분 탐색(binary search)이라는데 그것보다 스위핑처럼 하는 방법이 먼저 떠올라 그걸로 풀었다 방법은 이분 탐색만큼 간단한데 동물들의 점..