https://www.acmicpc.net/problem/15922 15922번: 아우으 우아으이야!! N개의 선분을 모두 그렸을 때, 수직선 위에 그어진 선분 길이의 총합을 출력한다아아어으잉에애야우아으아이아야아아아아아아이야!!! www.acmicpc.net 지문이 이게뭐에요 ㄷㄷ(혼란) 입력으로 들어오는 선분들을 싹 훑으면서(스위핑이다) 진행한다. 현재 이어지고있는 수직선의 구간을 $[s, e]$ 로 저장해 뒀을 때, 새로 입력으로 들어오는 $[x, y]$ 에 대해서 $x > N; for(int i=0; i> a >> b; p.push_back({a,b}); } int ans = 0; int s = p[0].x; int e = p[0].y; for(int i=1; i= p[i].x) e = max(p[..

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번 사대에서 맞출수 있는 동물을 매칭하면 O(NM)으로 시간초과를 받는다. 각 동물들에서 가장 가까운 사대를 O(lgM) 으로 매칭하고 이를 O(N)번 반복해서 전체 시간복잡도가 O(NlgM)이 되게하는게 정석적인 풀이 가장 가까운 사대를 O(lgM) 에 매칭하는데 있어서, 이분탐색을 사용해야 한다. V에서 K 이..

https://www.acmicpc.net/problem/17425 17425번: 약수의 합 두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더 www.acmicpc.net 약수의 합을 빠르게 구해야 하는 문제. 시간이 좀 타이트하니 fastio를 사용해주자. 약수의 합 f[i] 를 빠르게 구하기 위한 소스코드이다. 나눗셈 연산, 나머지 연산은 계산 속도가 좀 느린편이라 속도를 빠르게 하기 위해서 제일 기본적인 덧셈 연산만 사용하도록 소스코드를 작성해줘야 한다. for(ll i=1; i

https://www.acmicpc.net/problem/10158 10158번: 개미 가로 길이가 w이고 세로 길이가 h인 2차원 격자 공간이 있다. 이 격자는 아래 그림처럼 왼쪽 아래가 (0,0)이고 오른쪽 위가 (w,h)이다. 이 공간 안의 좌표 (p,q)에 개미 한 마리가 놓여있다. 개미는 오 www.acmicpc.net 개미의 위치를 구하는 문제. 시뮬레이션 태그가 붙을것 같이 생겼지만, t의 범위가 터무니없기때문에 다른 접근을 시도해야 한다. 우선 첫번째로, 초당 1칸씩 이동하기 때문에 이동거리를 (x+t) 와 같이 생각해볼 수 있다. x축과 y축을 분리해서 생각하는 것이 핵심이다. 개미가 y축 이동방향을 무시한다고 가정하면 개미는 x축에서 좌우의 벽에 튕기면서 이동하는 모습을 보일 것이고, ..

https://www.acmicpc.net/problem/17610 17610번: 양팔저울 무게가 서로 다른 k개의 추와 빈 그릇이 있다. 모든 추의 무게는 정수이고, 그릇의 무게는 0으로 간주한다. 양팔저울을 한 번만 이용하여 원하는 무게의 물을 그릇에 담고자 한다. 주어진 모든 추 www.acmicpc.net KOI 2019 중등부 1번 브루트포싱 문제였습니다. 단순하게 어떠한 추에 대해서 생각해볼 수 있는 세가지 경우 왼쪽에 놓는다 오른쪽에 놓는다 저울에 올리지 않는다 이 셋을 모두 고려해서 소스코드를 작성해주면 된다 전체 시간복잡도는 O(3^N)인데, N이 13으로 매우 작아서 160만번 정도밖에 계산하지 않는다. 왼쪽에 놓는 경우에 측정 가능한 무게 K (지문에서는 □로 표기) 는 줄어들게 되므..

https://www.acmicpc.net/problem/2961 2961번: 도영이가 만든 맛있는 음식 첫째 줄에 재료의 개수 N(1 ≤ N ≤ 10)이 주어진다. 다음 N개 줄에는 그 재료의 신맛과 쓴맛이 공백으로 구분되어 주어진다. 모든 재료를 사용해서 요리를 만들었을 때, 그 요리의 신맛과 쓴맛은 www.acmicpc.net 신맛과 쓴맛이 최대한 비슷해지게 만드는 문제. N이 10으로 매우 작아서 O(2^N) 시간복잡도를 가지는 브루트포스로도 문제를 해결할 수 있다. 해당 문제의 구현 방법으로는 재귀함수를 사용한 구현과(dfs-like) 비트마스킹을 이용한 구현이 있는데, 비트마스킹을 연습하기에 나쁘지 않은 유형이지 싶어서 비트마스킹으로 풀어보았다. i번 재료를 섞는 경우에 i번 비트를 1로 켜고..