목록Algorithm (121)
블로그 옮겼습니다
\(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] 구간에 어떤 수들이 ..
1234memset(d,0,sizeof(d)); for (i=0;i
이건dy[4] = {0, -1, 1, 0};dx[4] = {-1, 0, 0, 1};을 하여 상하좌우 dfs 돌릴 때 많은 쓰는것을 따로 dy,dx 를 선언하지않고 한줄에 처리하는것이다.. 그리고cout
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에 대해 메모이제이션한 것을 초기화해주고 다시 부분문..