PS 를 공부하자

문제 링크\(0\lt{N}\le{10^3}\)\(0\lt{K}\le{10^6}\)문제는 간단하다. N개의 사람이 있고 K개의 경기가 있다.모든 경기는 적어도 한명은 참가되어야하지만 딱 한사람만 참가할 수 있다.각 사람은 적어도 한 경기는 해야하고 한 사람은 여러개의 경기를 할 수가 있다.이 때 경기가 배정되는 경우의 수를 구하는 문제이다.우선 K가 10^6인건 훼이크라는 것을 알 수가 있다. 왜냐하면 K가 N보다 크면 모든 사람에게 적어도한경기씩 배..

문제 링크n, m, d (1 ≤ n ≤ 150000; 1 ≤ m ≤ 300; 1 ≤ d ≤ n).수직선에 1, 2, ..., n 의 장소가 있다. m 개의 폭죽이 임의의 시간과 장소에서 발사된다.주인공은 1초에 d만큼 이동할 수 있다. 시작 위치는 아무데서나 시작해도 된다.i번 폭죽이 발사될 때 주인공이 x 지점에 있을 때 얻게되는 행복은 \(b_i - |a_i - x|\) 이다.이 때 모든 폭죽이 발사되..

문제 링크N <= 10^5, K <= N이 문제는 N 이 주어지고 N개의 정수가 주어진다.N개의 정수 중에 일부만 골라서 합을 최대로 만들어야 하는데K개를 초과하여 연속된 수를 고를 수가 없다는 제약이 있을 때 최대 합을 구하는 문제이다.우선 dp 로 부분문제를 정의하고 점화식을 세워보자.psum[i] : 1~i 번째 수의 합dp[i] : i 까지 봐줬을 때 최대 합dp[i] = max(psum[i] - psum[j] + dp[j - 1]..

문제 링크\(1 <= N <= 10^7\)\(1 <= K <= N\)\(1 <= L <= 10^9\)원 모양에 L개의 구역이 있다. 나는 현재 구역0에 있고 구역0을 기준으로 시계방향으로구역1, 구역2, ..., 구역L-1이 있다. 구역L-1다음은 다시 구역0으로 돌아온다.즉, 구역L-1는 구역L-2와 구역0 과 인접한다. 인접한 구역으로 이동하는 데에는 1초가 걸린다.N개의 팀이 임의의 구역에 있다..

https://community.topcoder.com/stat?c=problem_statement&pm=11817A, B, X <= 200입력 A, B, X 가 주어진다.서로 다른 화폐가 두개 A, B가 있다. A와 B를 적절히 섞어서 지불할 수 있는 모든 금액을X, Y 로도 지불할 수 있도록 하는 X와 다른 Y의 개수를 구하는 문제이다.이 문제를 세가지 방법으로 풀어보았다.(N <= 200)풀이1 : O(N^3) 방법(..

https://community.topcoder.com/stat?c=problem_statement&pm=11781 n <= 50, w[i] <= 1000 n 이 주어지고 n개의 정수 w[i] 가 주어진다. n개의 칸이 있는데 특정 순서로 칸들을 지워서 점수를 최대로 하는 문제이다. 양쪽 두 칸은 지울 수 없다. k번째 칸을 지울 때 얻을 수 있는 점수는 w[k-1] * w[k+1] 이고 k를 지웠으면 번호를 0부터 다시 매긴다...

https://community.topcoder.com/stat?c=problem_statement&pm=11308 풀이를 떠올린 속도는 나쁘지는 않았는데 cache 의 초기값을 -inf 로 안주고 0으로 줬다가 디버깅하느라 시간이 좀 걸렸다.트리의 간선의 수 N이 정해지면 모든 노드들의 degree 의 합도 2N 으로정해지기 때문에 노드 수와 degree의 합이 N+1과 2N이 되게 하는 모든 degree의 조합의 최대 점수를 dp로 계산하..

https://www.acmicpc.net/problem/1804 2*B 격자에 음식이 N개 놓여져 있다. K개의 랩을 사용하여 음식을 덮을 때 덮이는 칸의 최소 개수를 구하는 문제이다. 랩은 어느 크기로든 늘리거나 줄일 수 있다. N <= 1000, K <= N, B <= 15000000 처음에 dp[l][r][k] : l~r 칸까지 k개의 랩으로 덮을 때 최소 덮이는 칸 수 로 생각했는데 좌표 압축을 해도 적어도 O(N^4..

https://www.acmicpc.net/problem/11570 N <= 200010^6 이하인 N개의 음이 주어지고 이 N개의 음을 두 사람이 나누어 부른다.음을 나누어 순서대로 놓았을 때ai 를 A가 i번째로 낸 음이라고하면 |\(a_i - a_{i-1}\)| 가 ai 를 낼 때의 힘든 정도이다.A와 B의 힘든 정도의 합을 최소로 하도록 음을 나누었을 때의 합을 구하는 문제이다.C[i] : i번째 음go(pos, lastA, las..

https://www.acmicpc.net/problem/14437 정수 S 와 문자열 str 가 입력으로 주어진다. S <= 3000, len(str) <= 3000 1. 임의로 문자열의 한 문자를 골라서 k(1<=k<=25)만큼 이동시킨다.(a를 3 이동 시키면 d, z를 1 이동시키면 a) 2. 한번 이동했던 문자는 다시 이동시키지 않는다. k의 합이 S가 될 때까지 1번을 반복했을 때 만들어 질 수 있는 문자열의 가..