yeongminb의 PS 블로그

문제 링크 문제 풀이 어떤 정점 $n\leq 21$개, 간선 $m$개의 그래프 위에 원숭이가 살고 있고, 매 턴마다 인접한 정점으로 항상 움직인다. 이때 매턴마다 그래프 위에 정점 하나를 골랐을 때 최악의 경우에도 언젠가는 원숭이를 잡을 수 있는지를 묻는 문제이다. 또 잡을 때까지의 최소 몇 번의 턴이 필요한지와 가능한 실례도 제시해야한다.   일단 문제를 보자마자 생각할 수 있는 것은 가능하기 위해서는 당연하게 이 그래프가 사이클이 없는 트리여야한다는 것이다. 만약 사이클이 있다면 그 사이클 위에 있는 원숭이는 매턴마다 두 가지의 선택지가 반드시 존재하므로 원숭이를 유인할 수 없다. 이는 직관적으로도 자명하다. 따라서 $m$이 $n-1$이 아닐 경우에는 볼 필요가 없어진다.  처음에는 트리인 경우는 모..

문제 링크 문제 풀이 이 문제는 어떤 양의 실수$\leq 10^9$들의 합에 대한 정보와 곱에 대한 정보가 주어질 때 이 수들의 개수로 가능한 최솟값을 출력하는 문제이다. 합과 곱이 주어졌으므로 산술기하 평균 부등식 AM-GM inequality 을 떠올릴 수 있다. 이 실수들의 합, 곱, 개수를 각각 $S, P, N$이라 할 때 다음이 성립한다.$$S \leq N\sqrt[N]{P}$$$$\Rightarrow P \leq (\frac{S}{N})^N$$  따라서 이를 만족하는 $N$의 최솟값을 찾으면 된다. 이때 불가능한 경우를 따지기 위해 $f(N) = (\frac{S}{N})^N$로 두고 미분하여 최댓값을 찾아야한다.$$(\ln_{}{f(N)})^{\prime}=\frac{f^{\prime}(N)}..

문제 링크 문제 풀이  이 문제는 $m\leq 500$ 개의 $10^8$ 이하의 숫자와 $k\leq m$ 이 주어질 때 $m$개의 숫자를 $k$개의 집합을 나누어 그 집합들의 합의 최대가 최소가 되도록 하는 문제이다. 이때 같은 집합에 포함되려면 그 수들이 모두 연속해야하며 원소에 개수가 1개 이상이어야한다. 예를 들어 9개의 수 100, 200, 300, 400, 500, 600, 700, 800, 900을 3개의 집합으로 나눈다고 할 때 100,200,300,400,500 / 600,700 / 800,900 으로 나눠야 최대합이 1700으로 최소가 된다. 참고로 나누는 방법이 여러개인 경우는 앞쪽의 집합의 원소의 개수가 가장 작을 때를 출력해야한다.  일단 $m,k$의 범위가 작아서 백트랙킹을 해야하..

문제 링크 문제 풀이 이 문제는 $4\times 4$ 크기의 그리드에 글자들이 적혀져 있을 때 이 글자들을 이어 만들 수 있는 단어들을 찾는 문제이다. 이때 찾은 단어의 길이에 따라 점수가 주어져 점수가 최대로 되도록 하게 찾기도 해야한다. 주어지는 단어의 개수는 $w \leq 3\times 10^5$이고 단어의 길이는 최대 8이다.  일단 칸의 개수가 16개로 매우 작은 편이기 때문에 DFS로 완전탐색 할 생각을 할 수 있다. 모든 칸에서 최대 $4^8$번 탐색을 하므로 연산 횟수는 $2^{20}$을 넘지 않는다. 그래서 그냥 완전탐색을 하며 중복만 잘 처리해주면 되는 아주 쉬운 문제이다. 참고로 실행시간 절약을 위해 주어진 단어들을 해시 맵 형태로 저장하였다.  코드#include #include #..

문제 링크 문제 풀이 이 문제는 정점의 개수 $N \leq 200$ 이고 간선의 개수 $M \leq 20000$ 인 그래프에서 특정한 정점에 불을 붙여 모든 정점과 모든 간선이 불에 탈 때까지 걸리는 최소시간을 출력하는 문제이다. 어떤 정점에 불이 붙으면  그와 연결된 모든 간선으로 불이 퍼져나간다. 이때 이 간선이 모두 불타는데 걸리는 시간은 그 간선의 길이와 같다. 또한 간선의 양쪽 정점에 모두 불이 붙은 경우는 두 불이 퍼져나가다 만나면 그 간선이 모두 불탄 것이다. 참고로 간선 중에는 양 끝 점이 모두 동일하게 한 정점인 간선도 있다.  처음 한 생각은 일단 모든 정점으로부터 모든 정점까지 최소 거리를 저장하는 것이다. 그렇게 되면 어떤 정점으로부터 불이 시작될 때 어떤 간선이 불에 타서 없어질 ..

문제 링크 문제 풀이 이 문제는 어떤 0과 1로만 구성된 문자열이 주어질 때 그 문자열의 서로 다를 필요는 없는 부분 문자열끼리 XOR연산을 한 값의 최댓값을 출력하는 문제이다. 여러개의 테스트 케이스로 주어지고, 이때 주어지는 모든 문자열의 길이의 합은 $10^7$을 넘지않아서 $O(N)$풀이가 필요하다.   문제를 처음봤을 때 아이디어가 바로 떠올라서 플레4보단 쉽다고 느꼈는데, 구현을 해볼 수록 고려해야할 게 많다는 것을 깨달았다. 생각한 아이디어는 앞의 나오는 자릿수 중에 1이 많으면 좋으므로, 처음에 나오는 연속한 1들과 그 다음 나오는 0들을 XOR하는 것이었다. 예를 들어 11100010이라는 문자열이 주어지면 11100010과 11100을 XOR하여 앞의 0들을 모두 1로 만들어주어 숫자를..

문제 링크 문제 풀이 이 문제는 $K \leq 50$개의 자연수 중에서 $N\space\space(K \leq N \leq 50)$개의 자연수를 중복을 허용하고 뽑아 이어붙였을 때 만들어질 수 있는 가장 큰 수를 출력하는 문제이다. 이 때 주어진 K개의 자연수 모두 적어도 한 번씩은 사용되어야한다.   이 문제를 접근할 때 두 가지를 고려하였다. 첫 번째는 주어지는 각 숫자의 사용 개수이고, 두 번째는 숫자들의 사용 순서이다. 먼저 각 숫자의 사용 개수는 당연히 자릿수가 가장 많은 숫자를 많이 사용하는 것이 유리하다. 왜냐하면 자릿수가 많을수록 숫자가 커지기 때문이다. 그래서 자릿수가 가장 큰 숫자를 $N-K$번 사용하고 나머지를 1번씩만 사용할 생각을 하였다. 만약 자릿수가 가장 큰 숫자가 2개 이상이..

문제 링크  문제 풀이 이 문제는 Hilbert Curve 모양의 미로에서 시작점까지의 거리가 주어질 때 그 위치의 좌표를 구하는 문제이다. 입력은 $n \leq 2^{15}$ 와 $m \leq n^2$ 이 주어지는데 $n$은 미로의 크기, $m$은 구하고자 하는 점의 시작점으로부터의 거리이다.   Hilbert Curve가 재귀적으로 정의되는 모양이다보니까 이 문제도 재귀적으로 풀어야겠다는 생각을 했다. 이 때 미로를 $\frac{n}{2}$ 크기의 네 구역으로 나누어서 분할정복 알고리즘으로 플 수 있다고 생각했다. 그래서 먼저 좌표를 반환해주는 함수를 다음과 같이 정의해보자.//pair : 크기 k인 미로에서 거리 d인 점의 좌표pair calcCoord(int k, int d)먼저 구하고자 하는 점..

문제 링크 문제 풀이 이 문제는 $1$부터 $N \leq 10^9$까지의 수에서 등장하는 0 ~ 9의 개수를 출력하는 문제이다. 문제 자체는 쉽지만 TLE가 나지 않게 구현을 하려고 하면 조금 까다로운 문제이다.  기본적인 아이디어는 $N$을 각 자리수에 따라 나누어 더블카운팅의 형식으로 세는 것이다. 예를 들어서 $N = 223$이라고 하면 $N$을 200, 20, 3으로 나누어서 0~199까지의 각 자리수의 개수, 0~19까지의 각 자리수의 개수, 0~3까지의 각 자리수의 개수를 따로 세주어 더하는 형식이다. 여기서 0~199까지의 각 자리수의 개수와 같은 경우는 또 0~99, 100~199로 나누어서 생각해볼 수 있다. 10의 거듭제곱 단위로 나뉘기 때문에 이에 대한 정보만 미리 저장해둔다면 빠른 ..

문제 링크  문제 풀이 이 문제는 $N \leq 1.5\times 10^6$일 동안 상담을 하는데 각 상담마다의 걸리는 시간과 얻을 수 있는 금액이 주어질 때 얻을 수 있는 최대 금액을 출력하는 문제이다. 상담을 하는 기간이 서로 겹치면 동시에 할 수 없기 때문에 적절한 상담들만 선택해주어야 한다.   문제를 보자마자 DP가 떠올랐다. 그런데 시작 날짜를 기준으로 DP를 하면 망할 것이 뻔히 보이기 때문에 상담 종료 날짜를 기준으로 DP를 할 생각을 쉽게 할 수 있다. 그러기 위해서 종료 날짜를 기준으로  각 상담들을 정렬해주고 상담의 시작날짜와 종료날짜를 이용해 선분처럼 표현하면 라인 스위핑을 하면서 DP를 해주면 풀릴 것이다.  점화식을 다음과 같이 정의하자. $dp[i] := (i$일 까지 상담을 ..

문제 링크  문제 풀이 이 문제는 $N \leq 10^{5}$개의 행성의 좌표 $x,y,z$가 주어지고 두 행성 $A(x_{A},y_{A},z_{A})$와 $B(x_{B},y_{B},z_{B})$ 의 거리가 $min(|x_{A}-x_{B}|,\space |y_{A}-y_{B}|,\space |z_{A}-z_{B}|)$로 정의될 때 모든 행성들을 연결하는 경로의 최소 길이를 구하는 문제이다.  처음 보자마자 당연하게 MST를 구해야겠다는 생각이 떠오른다. 그런데 MST를 구하는 Kruskal Algorithm을 쓰려고 하면 모든 간선의 개수가 ${N \choose 2}$개이므로 MLE랑 TLE가 날 수밖에 없다. 그래서 간선을 되도록 조금만 저장하는 방향으로 생각해볼 수 있다.  어짜피 MST에 포함되는 ..

문제 링크 문제 풀이 이 문제는 $N\leq 3\times 10^5$개의 보석과 $K\leq 3\times 10^5$개의 가방이 주어지고, 각 보석의 무게 $M_{i}$, 가격 $V_{i}$와 가방에 담을 수 있는 최대 무게 $C_{i}$가 주어질 때 담을 수 있는 보석의 최대 가격을 출력하는 문제이다.   일단 당연히 최대 가격을 얻기 위해선 보석들 중 가격이 높은 순서대로 가방에 넣는 것을 시도해야 한다. 그래서 그리디 알고리즘으로 생각해보면 가격이 높은 보석들부터 가방에 넣는데, 그 가방의 무게는 보석의 무게를 넘는 최소의 무게(lower bound)일 수록 좋을 것이다. 만약 만족하는 가방이 없거나 이미 보석을 넣은 상태라면 넣지 못할 것이다. 이렇게 생각하면 일단 보석에 대해 iteration을..

문제 링크  문제 풀이  이 문제는 수직선 위에서 가로등의 위치들이 주어질 때 각 수직선 상의 위치마다 밝기를 작은 것부터 $K \leqslant 3\times 10^5$개 출력하는 문제이다.   일단 $ L \leqslant 10^{18} $ 이므로 배열에 각 위치들을 배열에 저장하거나, 완전탐색을 할 경우 MLE나 TLE가 날 수밖에 없다. 그래서 필요한 위치들의 밝기만 저장하거나 다른 방법이 필요하다.  가장 처음에 생각했던 것은 인접한 가로등 사이의 구간 길이를 저장하는 것이다. 구간의 길이의 개수는 항상 $N+1$개이고, $N \leqslant 3\times 10^{5} $ 이기 때문에 완전탐색을 해도 별 문제가 없고, 구간의 길이가 각 위치들의 밝기를 특정해주기 때문이다. 예를 들어서 구간의 ..

문제 링크 문제 풀이 이 문제는 $N\times M$ 칸에 숫자들이 적혀 있을 때, 테트로미노 타일을 이용해 타일이 포함하는 수들의 합의 최댓값을 구하는 문제이다.  여기서 테트로미노는 폴리노미노의 한 종류로 네 개의 정사각형이 변끼리 인접하여 만들어지는 도형을 의미한다.    $N,M ≤ 500$ 이라서 그냥 브루트포스로 모든 점들에 대해서 백트랙킹으로 탐색해줘도 충분하다. 이때 시간복잡도는 $O(MN)$인데, 정확히는 백트랙킹 할 때 최대 $4^4$ 개의 가짓수가 있어서 $256MN$만큼의 연산이 필요하다.  먼저 Back Tracking 함수를 먼저 구현해보자. 초기 좌표와 깊이, 그리고 현재까지 숫자의 합을 매개변수로 하였다.void BT(int x, int y, int depth, int k){..

문제 링크   "물리학" 카테고리에 있는 문제들을 풀어보다가 이 문제가 재미있게 생겨서 풀어보았다. 예전에 이런 충돌수에 관련된 문제를 3Blue1Brown 이라는 굉장히 좋은(?) 채널에서 본 적이 있다.유튜브 영상 이 영상에서는 두번째 물체의 질량이 100의 거듭제곱 꼴일 때 충돌횟수가 π의 앞의 자리수가 되는 이유를 설명해주고 있는데 예전에 흥미롭게 봤던 경험이 있어서 생각이 났다.  1. 문제 풀이 먼저 알아야할 것은 두 번째 물체의 초기속력이 0만 아니라면 충돌수에 영향을 주지 않는다는 것이다. 만약 첫 번째 물체의 초기속력이 있었다면 상관이 있겠지만 첫 번째 물체의 초기속력이 0이므로 두 번째 물체가 어떤 속력을 가지든 속력비율은 항상 일정하기 때문이다. 근데 소수점계산에서 오류가 발생할 수도..