상위 99.99%의 PS

www.acmicpc.net/problem/17291 17291번: 새끼치기 실험실에서 새로운 종의 벌레 한 마리가 탄생하였다. 벌레는 스스로 분열하며, 분열하면 자기 자신과 같은 벌레를 한 마리 만들어 내게 된다. 벌레가 분열하는 규칙은 다음과 같다. 벌레는 기준 www.acmicpc.net dp로 풀 수 있고, 단순 구현으로도 풀수 있다. 나는 dp로 풀었다. 홀수년도와 짝수년도에 태어난 세포는 모두 짝수년도에 소멸하고, 소멸하는 수는 그 전년도의 세포의 수이다. 즉, i 년에 태어난 세포의 수 = (i - 1)년에 존재한 세포의 수이다. 점화식은, k가 짝수일 때, \(dp[k] = dp[k-1] * 2 - (dp[k-4] + dp[k-5])\) k가 홀수일 때, \(dp[k] = dp[k-1] *..

www.acmicpc.net/problem/1321 1321번: 군인 첫째 줄에 부대의 개수 N(1 ≤ N ≤ 500,000)이 주어지고, 이어서 각 부대의 군사 수를 나타내는 정수가 N개 주어진다. 각 부대의 군사 수는 1000보다 작거나 같은 자연수이다. 그 다음 줄에 명령의 개 www.acmicpc.net 세그트리 기초문제?이다. 1~K번째 부대 인원의 수의 총합을 A_k라고 할때, x번 군인의 위치는 \(A_{k-1} \lt x \le A_k\) 를 만족하는 가장 작은 k가 되고, 이는 이분 탐색으로 빠르게 구할 수 있다. -소스코드 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 3..

www.acmicpc.net/problem/16895 16895번: 님 게임 3 구사과와 큐브러버가 님 게임을 하고 있다. 님 게임은 돌을 위로 쌓아올린 돌 더미 k개를 이용한다. 각각의 돌 더미에는 한 개 이상의 돌이 있다. 두 사람은 서로 턴을 번갈아가면서 님 게임을 진 www.acmicpc.net Sprague-Grundy Theorem.. 재밌다. O(MN^2) 로 브루트포스 돌리면서 님 합이 0이 된다면 ans에 1 더하는 방식으로 풀었다. 1 2 3 4 5 6 7 8 9 10 11 12 13 n = int(input()) a = list(map(int, input().split())) ans = 0 for i in range(n): for j in range(1, a[i]+1): p = a[i..

www.acmicpc.net/problem/17371 17371번: 이사 $(\frac{2}{3}, \frac{1}{3})$으로 이사를 가면 가장 가까운 편의시설은 (0, 1)으로 거리는 $\frac{2\sqrt{2}}{3}$이고, 가장 먼 편의시설은 (-4, 1) 혹은 (4, -3)으로 거리는 둘 다 $\frac{10\sqrt{2}}{3}$이다. 두 거리의 www.acmicpc.net 편의시설을 집으로 쓸 수 없다는 조건이 없기 때문에, 문제가 매우 쉬워졌다. 그냥 편의시설을 집으로 쓰면 된다. 집과 가장 가까운 편의시설의 거리는 0이 되므로, 가장 먼 편의시설과의 거리만 계산해주면 O(N^2)에 풀 수 있다. N제한도 1000밖에 되지 않아 충분하다! 집을 편의시설로 정하는게 왜 되는건지는 직접 증명..

www.acmicpc.net/problem/13263 13263번: 나무 자르기 첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 둘째 줄에는 a1, a2, ..., an이, 셋째 줄에는 b1, b2, ..., bn이 주어진다. (1 ≤ ai ≤ 109, 0 ≤ bi ≤ 109) a1 = 1이고, bn = 0이며, a1 b2 > ... > bn을 만족 www.acmicpc.net CHT 기초문제이다. 아래 자료를 먼저 읽고 온다면 도움이 된다. stonejjun.tistory.com/50 m.blog.naver.com/PostView.nhn?blogId=kks227&logNo=221418495037&proxyReferer=https:%2F%2Fwww.goog..

www.acmicpc.net/problem/8911 8911번: 거북이 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 컨트롤 프로그램이 주어진다. 프로그램은 항상 문제의 설명에 나와있는 네가지 명령으로만 이루어져 www.acmicpc.net 단순 구현문제다. 거북이가 간 점들의 최대, 최소가 되는 x좌표와 y좌표로 직사각형의 넓이를 구할 수 있다 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 import sys input = sys.stdin.readline t = int(input()) def fr(): k[0] = min(no..

www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 중앙값을 기준으로 우선순위 큐 두 개를 만들어주고 풀었다. 코드 더러워지는거 싫어서 hpp = heapq.heappop hps = heapq.heappush 라고 미리 써두고 풀었다 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 import heapq, sys input = sys.stdin.readline hpp..

https://www.acmicpc.net/problem/3344 3344번: N-Queen 첫째 줄에 N이 주어진다. N은 8, 26, 213, 2012, 99991, 99999중 하나이다. www.acmicpc.net www.acmicpc.net/problem/21133 21133번: N-Queen 2 N개의 줄을 출력해야 한다. i번째 줄에는 하나의 정수를 출력해야 하고, 이 정수는 i번째 행에 있는 퀸이 있는 열의 번호이다. www.acmicpc.net 왜 또 constructive지? 3344랑 코드는 같다. 6k+2, 6k+3에서 안되는거 알고 찾다가 도저히 모르겠어서 위키에서 찾고 그대로 구현했는데.. 좀 그렇다... 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17..

www.acmicpc.net/problem/20913 20913번: Mixtape Management Output $n$ distinct integers in lexicographically increasing order, your sequence of filenames. All numbers must be positive integers less than $10^{1000}$ and may not contain leading zeroes. Any valid sequence of filenames will be accepted. www.acmicpc.net 이런 구성적은 재밌어서 좋다 노트에 조금 끄적이다 보면 두 개의 숫자만으로도 풀수있다는 사실을 금방 알 수 있다. 나는 1과 2로 풀었다. n번째 단..

www.acmicpc.net/problem/19240 19240번: 장난감 동맹군 당신은 N개의 동물 장난감을 이용하여 모의 전쟁 놀이를 하려고 한다. 장난감은 편의상 1부터 N까지 번호가 붙어있고, 당신은 이를 두 개의 동맹군으로 나누고 싶다. 다만 특정 장난감끼리 사 www.acmicpc.net [DFS를 이용한 내 풀이] 1번 정점부터 dfs를 돌며 방문하지 않은 정점에 대해 팀의 색을 돌아가면서 입혀주었다. 그 후, 모든 간선에 대해 두 정점의 색이 같은지 확인해주었다. 파이썬으로 하니까 터져서 c++로 풀었다. [소스 코드] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 ..