https://www.acmicpc.net/problem/3649 3649번: 로봇 프로젝트 각 테스트 케이스마다 한 줄에 하나씩, 구멍을 완벽하게 막을 수 있는 두 조각이 없다면 'danger'를 출력한다. 막을 수 있는 경우에는 'yes ℓ1 ℓ2'를 출력한다. (ℓ1 ≤ ℓ2) 정답이 여러 개인 경우에 www.acmicpc.net 이분탐색 문제 std::unordered_map 쓰면 날로먹을수있을거같이 생겨먹었는데 왠지 모를 이유로 잘 안풀려서 이분탐색으로 해결했다. 둘의 합이 X*10000000 = K 가 되게 해야하기 때문에, 어떤 한 수를 정해줬다면 해당 수와 더해서 K가 되게끔 하는 수를 O(logN) 시간에 찾아야 한다. 찾아내는 가장 좋은 방법은 이분탐색. 이때, 어떤 한 수 a가 한개밖..

boj 1182 부분수열의 합 에서 범위를 두배로 키운 문제. https://www.acmicpc.net/problem/1208 1208번: 부분수열의 합 2 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 밋인더 미들 알고리즘을 사용한다. boj 1182에서와 같이, N이 20일때는 모든 경우에 대해서 브루트포싱할때 전체 연산 횟수가 백만 정도여서 깔끔하게 해결이 가능하지만, N이 40인 이 문제에서는 전체 연산 횟수도 백만의 제곱이어서 시간초과를 받게 된다. 시간초과를 방지하기 위해 입력으로 들어..

https://www.acmicpc.net/problem/11058 11058번: 크리보드 N = 3인 경우에 A, A, A를 눌러 A 3개를 출력할 수 있다. N = 7인 경우에는 A, A, A, Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V를 눌러 9개를 출력할 수 있다. N = 11인 경우에는 A, A, A, Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V, Ctrl-A, Ctrl-C, Ctrl www.acmicpc.net DP 문제. DP[i] 를 버튼을 i번 눌러서 화면에 출력할 수 있는 A 개수의 최댓값으로 만든다. DP[i] 의 기초 값은 DP[i-1] + 1 이다. ( 1번 버튼 화면에 A를 출력한다를 사용 ) 2, 3, 4번 연산은 사실상 한 세트라고 생각하면 되는데, 어..

https://www.acmicpc.net/problem/19539 19539번: 사과나무 첫 번째 줄에 모든 나무가 갊자가 바라는 높이가 되도록 물뿌리개를 통해 만들 수 있으면 “YES”를, 아니면 “NO”를 따옴표를 제외하고 출력한다. www.acmicpc.net 굉장히 빠르게 풀어내서 만족스러운 문제. 일단 쉽게 관찰할 수 있는 첫번째 특징으로, 입력으로 들어온 $h_k$ 들의 합 $sum$ 이 반드시 3의 배수여야만 한다. 두 물뿌리개를 동시에 사용하면 물이 3만큼 뿌려지게 되기 때문이다. 예제 입력 4로 설명해주고 있는 또다른 조건의 하나로, 이 조건으로 인해 골드5라는 티어를 배정받지 않았나 싶다. 나무 하나를 2만큼 성장시키는 물뿌리개는 아무리 뿌려도 짝수 높이만큼의 나무를 만들 수 있기 때..

https://www.acmicpc.net/problem/2643 2643번: 색종이 올려 놓기 첫 번째 줄에는 색종이의 장수가 주어진다. 다음 줄부터 각 줄에 색종이의 두 변의 길이가 주어진다. 두 변의 길이는 한 칸 띄어 주어진다. 색종이의 최대 장수는 100이고, 각 변의 길이는 1000보다 www.acmicpc.net DP 문제. DP[i] 를 i번 색종이를 제일 위에 쌓을때 최대 장수로 정의한다. dp[i]를 구하는 방법은 i번 색종이 밑에 놓일 수 있는 보다 큰 색종이 k에 대한 dp[k] 와 비교를 해서, dp[i] = max(dp[i], dp[k]+1) 식으로 계산해주면 된다. 이때, k를 보다 빨리 찾고 편하게 비교하기 위해서, 입력으로 받는 색종이를 일괄적으로 가로 / 세로로 방향을 고..

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 (지문에서는 □로 표기) 는 줄어들게 되므..