상위 99.99%의 PS

https://www.acmicpc.net/problem/3056 3056번: 007 비밀 요원 007은 제임스 본드로 유명한 비밀 요원이다. 최근 알려진 정보에 의하면 제임스본드는 대다수 미션을 자신이 직접 수행하지 않는다고 한다. 본드는 미션을 자신과 비슷하게 생긴 사촌 www.acmicpc.net DP Using Bitfield dp[bit] = (상태 bit에서의 최대 확률) 이라고 정의하자. dp[bit] = max(dp[bit], f(x + 1, bit | (1 =1 return ret def getInv(x): return getPow(x, MOD-2) Colored by Color Scripter cs 1 2 3 4 5 6 7 8 9 10 11 12 13 14 dp = [-1 for _ i..

https://www.acmicpc.net/problem/1311 1311번: 할 일 정하기 1 N명의 사람과 N개의 일이 있다. 각 사람은 일을 하나 담당해야 하고, 각 일을 담당하는 사람은 한 명 이어야 한다. 또한, 모든 사람은 모든 일을 할 능력이 있다. 사람은 1번부터 N번까지 번호가 매 www.acmicpc.net DP Using Bitfield dp[n][bit] = (n번째에서 상태가 bit일 때 최소 비용) 이라고 정의하자. dp[n][bit] = min(dp[n][bit], f(n + 1, bit | (1 =1 return ret def getInv(x): return getPow(x, MOD-2) Colored by Color Scripter cs 1 2 3 4 5 6 7 8 9 10..

https://www.acmicpc.net/problem/11574 11574번: CYK의 너무너무 재밌는 그래프 만들기 놀이 N (1 ≤ N ≤ 100)개의 정점의 개수가 주어지고, K (1 ≤ K ≤ 3)개의 가능한 색깔이 주어진다. 각 정점들을 1 부터 N까지 차례로 번호를 매기고, 그 정점들에 K개의 색깔중 하나를 임의로 부여한다. www.acmicpc.net 간단한 DP k = 1일때 무조건 1가지이다. k = 2일때 맨 뒤에 색 1 추가, 혹은 색 2를 추가하는 경우가 있다. \(dp[n][k] = n번째에서 색 1을 k개 사용하였을 때, 경우의 수\) 라고 하자. 색 1을 붙일 때: 간선을 잇는 경우는 색 2의 개수이고, 잇지 않는 경우는 1가지이므로, \(dp[n - 1][k - 1] * ..

https://www.acmicpc.net/problem/14700 14700번: 넴모넴모 (Hard) 첫 번째 줄에 주어진 격자판에서 나올 수 있는, “넴모”들이 올라간 칸이 2 × 2 사각형을 이루지 않는 모든 배치의 가짓수를 1, 000, 000, 007로 나눈 나머지를 출력한다. www.acmicpc.net 파이썬으로 시간 터져서 못했음 파란색 칸을 채우기 위해서는 \((M + 1)\) 개 칸의 상태 정보가 필요하다. 파란색 칸을 채우지 않는 경우: => 항상 채우지 않는 선택을 할 수 있다. 채우는 경우: - 가장 왼쪽 칸일 경우: => 항상 채울 수 있다. - 가장 왼쪽 칸이 아닐 경우: => 왼쪽, 왼쪽 위, 위의 3개의 칸이 모두 색칠되지 않았다면 채울 수 있다. 1 2 3 4 5 6 7 ..

www.acmicpc.net/problem/14180 14180번: 배열의 특징 첫째 줄에 N (2 ≤ N ≤ 200,000)이 주어진다. 둘째 줄에는 Ai (|Ai| ≤ 1,000,000)가 주어진다. www.acmicpc.net 배열 t에서, \(A_{i} = t_{1} 부터 t_{i} 의 합\) B = 배열 t의 특징 이라고 하면, 배열 t의 n번째 수를 옮길 떄의 최댓값을 dp[n]이라고 하면, 이 n번째 수를 옮기는 방향에 따라 두가지로 나누어 풀면 된다. 왼쪽으로 옮길 때는, \(i= getX(k[-3], k[-2]): k.pop(-2) def bs(x): lo = 0 hi = len(k) - 2 while lo

www.acmicpc.net/problem/2315 2315번: 가로등 끄기 첫째 줄에는 2개의 정수 N(1 ≤ N ≤ 1,000), M 이 있다. 첫 번째 정수 N은 가로등의 개수를 나타내는 정수이고, 두 번째 정수 M은 마징가 처음에 위치하는 가로등 번호이다. 다음 N 개의 줄에는 각 가 www.acmicpc.net dp 진짜 개재밌게 풀었다. 이동은 바로 옆의 켜진 가로등으로만 하는 것이 이득이다. dp테이블은 구간 \([l,r]\)에서, 내 위치가 \(x\)일때 최솟값으로 나타내면 된다. 공간은 1000*1000*2를 사용한다. 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 impor..

www.acmicpc.net/problem/16991 16991번: 외판원 순회 3 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 도시의 좌표 x, y가 주어진다. 모든 좌표는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. 두 도시의 위치가 같은 경우 www.acmicpc.net DP using bitfield 외판원 순회 1과 똑같은 문제이다. 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 37 import sys from math import sqrt input = sys.stdin.readline INF = 1234..

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/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/20531 20531번: 인간관계 S인터넷고등학교에는 $N$명의 학생이 있다. 이들 사이에 몇몇은 서로 친구 관계를 맺고 있다. 친구 관계는 다음 세 가지 조건을 만족한다. 모든 학생은 자기 자신의 친구이다. 학생 $x$가 학생 $y$ www.acmicpc.net 벨 수를 알고있으면 좋다. union find를 활용한 dp문제이다. 차근차근 풀어보자 1. 점화식 dp[i][j] = (i개의 그룹을 j개로 묶는 경우의 수) 라고 하면, dp[i][j] = dp[i-1][j] * j + dp[i-1][j-1] 라고 점화식을 세울 수 있다. 나는 미리 dp 배열을 채워두고 시작했다. 2. 그룹의 수 세기 그룹의 개수를 n으로 두고 시작해보자. 두 사람이 입력으로 주어..