블로그 옮겼습니다

https://oj.uz/problem/view/KRIII5_YZ $1\leq{N,M}\leq{400}$N x M 의 격자가 주어진다. 격자의 각 칸은 'B' 또는 'W' 이다.이 격자를 상하좌우대각선으로 무한히 이어붙였을때 무늬가 나타날 것이다. 여기에는 같은 색끼리 상하좌우로붙어있기도하고 혼자있기도 할텐데 이 같이 붙어있는 수를 각 칸마다 구하는 문제이다. 무한히 많은 같은색 칸이붙게 되는 칸은 -1 을 출력한다.예를 들어 이 경우에는 답이2 2 -1-1 -1 -1이 된다.흰 칸들은 모두 무한히 이어지며, 검은칸들은 각각 두개씩 붙어있기 때문이다. 그럼 이문제를 어떻게 풀까?dfs로도 풀 수가 있겠지만 구현도 쉽고, 예외처리해줄것도 적어 깔끔한 유니온 파인드로 풀어보자.모든 칸들에 대해 상하좌우와..

$1\leq{N}\leq{24}$$10^6\leq{P[i]}\leq{4\cdot{10^7}}(0\leq{i}\lt{N})$맨션의 개수 N이 주어지고, 각 맨션의 가격 P[i] 가 주어진다. 두 사람이 이혼을 하는데 맨션을 나눠 가지려 한다.각 맨션은 남자가 갖거나, 여자가 갖거나, 둘 다 안갖고 부동산에 팔거나 셋중 하나이다.이 때 남자가 갖게되는 맨션들의 가격의 합과 여자가 갖게되는 맨션들의 가격의 합이 무조건 같도록맨션을 나누고 싶다. 대신 가능한한 부동산에 파는 맨션의 가격을 최소화하고 싶다. 이 때 부동산에 팔아야하는맨션들의 가격의 합을 구하는 문제이다. 일단 naive 하게 각 맨션이 여자가 가짐,남자가 가짐,부동산에 팜 셋중 하나니까 3가지의 경우의 수가 있고N개의 맨션이 있으므로 O(..

https://community.topcoder.com/stat?c=problem_statement&pm=11634 $1\leq{N}\leq{40}$o와 x로 이루어진길이가 N인 문자열 S가 입력으로 들어올 때, 이 문자열에 포함된 각각의 문자들에 대해서 s1문자열 맨뒤에 붙일것인지s2문자열 맨뒤에 붙일것인지를 결정한다. 그리고 최종적으로 s1과 s2가 같게 만드는 방법의 수를 모두 구하는 문제이다.참고로 각 문자들은 구분할 수가 있기 때문에 최종 문자열이 같더라도 S상에서의 위치로 변환해봤을 때다르다면 방법이 다른것이므로 둘 다 셀 것이다. 우선 naive 하게 생각하여 모든 경우의 수를 세면서 두 문자열을 비교하여 같다면 더해주는 방식이 있을 것이다.이 방법은 우선 각각의 문자가 어떤 문자열에 들..

https://www.acmicpc.net/problem/10166 $1\leq{D1}\leq{D2}\leq{2000}$이 문제는 가운데에 콘서트장이 있고 그 주위로 동심원들이 있을 때, D1, D2가 입력으로 주어지면각 원내에서 거리가 일정하게 D1, D1+1, D1+2, D1+2, ... , D2 개를 각각 놓고 싶을 때 겹치는 위치가 있다면앞이 잘 보이지 않으므로 맨 앞에 한 좌석만 남기고 뒤에 좌석은 배치하지 않는 것이다.이 때 총 필요한 좌석의 수를 구하는 문제이다. 사실 동심원이 여러개 있는 것이 아니라 원이 하나 있고 그 안에 거리가 일정하도록 D1개의 점을 찍고그 다음에 같은 원에 거리가 일정하도록 D1+1개의 점을 찍고 를 계속 반복했을 때 찍히는 점의 수를 구하는 것과 같다. 우선 ..

https://www.codeground.org/practice/practiceProbView.do?probId=36 $1\leq{M}\leq{N}\leq{500}$ N은 집의 개수 M은 재활용 쓰레기 통의 개수.수직선상의 N개의 집의 좌표가 주어질 때 M개의 쓰레기통을 적절히 배치하여각 집에서 가장 가까운 쓰레기통까지의 거리의 합이 최소가 되도록 하고 싶을 때 이 최소값을 구하는 문제이다. 일단 거리의 합이아니라 거리의 최대값이 최소가 되도록 하는 문제 같은 경우에는바이너리 서치(파라메트릭서치)로 풀 수가있다. 그리고 이 문제는 dp로 풀 수 있다. 우선 몇가지 정의를 하자. (모든 집들은 좌표로 오름차순 정렬되어있다고 가정) $X[i]$ : i번째 집의 좌표$C[i][j]$ : i번째 집부..

$1\leq{N}\leq{1000}$$1\leq{K}\leq{4\cdot{10^{7}}}$$1\leq{w}\leq{10^7}$ 4개의 반이 있고 각 반의 학생수는 N명이며, 각 학생들의 몸무게 w 가 주어진다.반 마다 한명 씩을 골라서 총 네명의 선수를 선발하는데 네 선수의 몸무게의 합이 K와 가장 근접하도록선수들을 선발하여 그 몸무게의 합을 구하는 문제이다. 만약 답이 여러개라면 그중 작은 값을 답으로한다. 우선 가장 무식하게 푸는 방법이 완전탐색을 하는 방법이며 O(N^4) 이 걸린다. N이 최대 1000이기 때문에무리가 있다. 그런데 조금만 생각을 해보면 세 개의 반에서 선수가 골라졌다면 남은 한 반에서는K와 가장 가까운 학생을 고르면 되기 때문에 K-(세 반에서 뽑은 학생들의 몸무게의 ..

https://www.acmicpc.net/problem/1044 $2\leq{N}\leq{36}$ (N은 짝수) N을 입력받고, 10^15 이하인 자연수를 N개씩 두줄 입력받는다. N명의 사람은 1번팀 또는 2번팀에 들어간다. 각각의 사람이 어떤 팀에 들어갈 때 증가하는 팀의 전력이 주어진다.1번팀과 2번팀가 같은 수의 팀원을 가지며 두 팀의 전력차가 최소가 되도록 팀을 배정할 때 각각의 사람이 어떤팀에들어가게 되는지를 구하는 문제다.(만약 두 팀의 전력차가 같은 답이 여러개 있을 경우 사람들의 팀을 순서대로 나열한sequence 가 사전순으로 앞서는 것을 출력. 예를 들어 2 1 1 2 와 2 1 2 1 이 있으면 2 1 1 2 를 출력) 일단 naive 하게 생각해 보면 N이 최대 36이기 때문..

$2\leq{N}\leq{50}$$0\leq{A[i]}\leq{N-1}$N개의 원소로 이루어진 벡터 A가 주어진다. 벡터의 값들은 0과 N-1 사이값이며 중복되지않는다.$0\leq{K}\leq{N-2}$인 N-1가지의 K에 대해 각각 한번씩 swap(A[K], A[K+1]) 을 해야만 한다.그렇다면 이 swap을 하는 순서에 따라서 주어진 벡터의 결과값이 달라질 것이다.그렇다면 주어진 벡터가 0,1, ..., N-2, N-1 과 같은 형태로 오름차순 정렬되도록 하는 swap 순서는 총 몇가지가 있는지를구하는 문제이다. 이 문제는 DP로 풀 수가 있다. $dp[i][j]\,:\,[i,\,j]$ 의 구간을 오름 차순 정렬하는 방법의 수오름 차순 정렬이라는 것은 [i, j] 구간에 어떤 수들이 ..

https://oj.uz/problem/view/KRIII5_UV $1\leq{N}\leq{10^4}$$-10^{14}\leq{A[i]}\leq{10^{14}}$N이 주어지고 N개의 정수로 이루어진 배열 A가 주어진다.이 배열을 여러개로 나누는데 나눈 각각의 덩어리에 속한 원소의 합이 같도록 나눠야한다.이렇게 나누는 모든 방법의 가짓수를 구하는 문제이다. 물론 1e7 로 나눈 나머지를 구한다. 이 문제는 dp 문제이다. 각 덩어리의 원소의 합을 몇으로 같게 할지를 먼저 정해주고K로 정했다면 합이 K 가 되도록 나누는 방법의 수를 dp로 구한다.dp[i] : i번째 원소부터 합이 원소들의 합이 K인 덩어리들로 나누는 방법의 수그리고 모든 가능한 K에 대해 메모이제이션한 것을 초기화해주고 다시 부분문..

https://oj.uz/problem/view/KRIII5P_3 $1\leq{N}\leq{10^5},\,0\leq{s_{i},\,e_{i}}\leq{10^9}$N개의 구간 $[s_{i},\,e_{i}]$ 가 입력으로 주어질 때($s_i\gt{e_i}$ 면 공집합)구간들의 교집합이란 $[max(s_1,\,s_2,\,\cdots,\,s_k),\,min(e_1,\,e_2,\,\cdots,\,e_k)]$구간의 길이는 $max(0,\,e_{i}-s_{i})$ 으로 정의 될 때선택된 구간들의 교집합의 길이가 1이상이도록 구간들을 선택할 때그 선택하는 방법의 수와 그 각각의 방법에서 교집합의 길이들의 합을 구하는 문제이다. 우선 방법의 수는 라인 스위핑으로도 풀 수 있고, 좌표압축+펜윅트리로도 풀..