블로그 옮겼습니다

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3138 정말 좋은 문제인것 같다. 풀이

https://uva.onlinejudge.org/index.php?option=onlinejudge&Itemid=99999999&page=show_problem&category=&problem=4075 해석이 너무 안돼서 제대로 이해하는데 엄청 오래걸렸다.. \(5\leq{N}\leq{2\cdot{10^4}}\)\(0\leq{M}\leq{2\cdot{10^5}}\)N은 회사의 수, M은 쿼리의 수N개의 회사는 각각 센터를 가지고 있다. 이 회사들의 일부를 병합을 하여 하나의 더 큰 덩어리로 만드는 동시에센터는 하나로 유지를 하려고 한다. 병합을 할 때에는 하나의 덩어리의 센터에서 나머지 덩어리의 아무 회사로도로를 놓으면서 병합을 한다. 도로의 길이는 회사 a와 b를 이을 때 | a - b| mod 10..

문제들 중에는 특정 조건을 가진 시간과 분을 hh:mm 의 포맷으로 출력하거나 리턴하기를 원하는 문제들이 있다.이럴때 괜히 쓸데없는곳에 시간과 노력을 낭비하지 않기 위해 좋은 방법이 있다.1sprintf(out, "%02d:%02d", h, m);cs 사실 너무 기초적인 것이지만 오랫동안 별로 쓸 일이 없었던 것이라 잊고있었다..이걸 모르면 이런 상황이 발생할 수가있다..123456string ret;if(h

https://community.topcoder.com/stat?c=problem_statement&pm=11514 \(1\leq{N}\leq{50}\)\(1\leq{C}\leq{N}\)\(1\leq{L}\leq{50}\)문자열의 개수 N개와 N개의 알파벳 소문자로만 이루어진 문자열이 주어지고,C와 L이 주어지는데, 길이 L의 문자열을 만들고 싶은데, 이 만들어진 문자열 내에 N개의 문자열들 중딱 C가지만 등장하도록 만드는 모든 문자열의 가짓수를 구하는 문제이다.우선 N가지의 문자열들 중 딱 C가지만 등장하는지 여부를 판단하려면 N개의 문자열을 동시에 하나의 긴 문자열에서등장하는지 찾아주는 알고리즘인 아호코라식 알고리즘이 필요하다는 것을 느낄 수가 있으며,N가지 중 지금까지 몇가지가 등장했는지를 알아야 ..

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-(세 반에서 뽑은 학생들의 몸무게의 ..