블로그 옮겼습니다

\(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개의 점을 찍고 를 계속 반복했을 때 찍히는 점의 수를 구하는 것과 같다. 우선 ..