klimmek55

돌맹이 제거 (http://boj.kr/1867) 요즘 기초적인 이분 매칭 문제들을 보고 있는데, 이분 매칭이라는 분류를 안 보면 알아차리기 힘들 것 같다. 그냥 왠지 안 풀리면 의심해봐야겠다. 이 문제에서는 $i$행 $j$열에 돌맹이가 있다면, $i$행을 청소하거나 $j$열을 청소해야 한다. 즉, 둘 중 하나를 선택해야 한다. 그래프는 행을 청소하는 경우, 열을 청소하는 경우로 나뉘고, $i$행 $j$열에 돌맹이가 있다면 $i$행과 $j$열을 이어준다. 그리고 $i$행에서 $j$열을 매칭하는 것은 $i$행을 청소하거나 $j$열을 청소하는 것이다. 만약 매칭할 수 있는게 여러가지라면 $i$행을 청소할 것이고, 한 가지라면 $j$열을 청소하게 될 것이다. ..

더위 피하기 (http:/boj.kr/15938) 좌표가 -100,000이상 100,000 이하라서 좌표 모두 배열을 만들어줄 수는 없다. 하지만 더위를 버틸 수 있는 시간이 200밖에 안 된다. 즉, 출발지에서 거리가 200이 넘는 곳은 어차피 갈 수가 없다.그러므로 출발지에서 거리가 200 이내인 곳만, 출발지에서 상대적인 위치로 생각하면 된다. 그리고 BFS로 경우의 수를 센다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768#include using namespace std; const long long r = 1e9 ..

Thinking Heap (http://boj.kr/15942) 방법은 여러가지가 있을 것 같다. 나는 이동이 전혀 일어나지 않도록 만들었다. 그 노드에 수를 넣었다면, 부모들은 자신보다 작아야하고, 자식들 중에 자신보다 작은건 없어야 한다. 어떻게 넣을지는 상관없다. 나는 자신보다 작아야 하는 수는 1부터 넣었고, 커야 하는 수는 n부터 넣었다. 그리고 상관없는건 남는 수들을 아무렇게나 넣었다. 불가능한 경우는 당연하게도, 작아야 하는 수의 개수가 자신보다 작은 수보다 많을 때와 커야하는 수의 개수가 자신보다 큰 수보다 많을 때이다. 그 외의 경우는 모두 가능하다. 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 2..

카드 팩 구매하기 (http://boj.kr/15823) 이분탐색 간단한 문제들도 이분탐색인줄도 모르고, 알아도 답을 어떻게 체크할지 몰라서 못 풀때가 많았는데 왠지 이건 바로 떠올랐다. 쉬운 편인가?카드 팩에 들어갈 카드 수를 기준으로 이분탐색한다. 넣을 카드 수를 정했으면, 가능한지를 확인해야 한다. 우선, 왼쪽이나 오른쪽부터 봤을 때 카드팩을 만들 수 있으면 만드는 것이 무조건 이득이다. 그러므로, 슬라이딩 윈도우의 느낌으로 카드팩을 만들 수 있는지 확인한다. 각 수가 등장한 위치를 체크해두고, 그 수가 또 등장했을 때 현재 카드팩 안에 있다면 그 뒤부터 카드팩을 만들면 된다. 개수를 채웠다면, 그 다음부터 카드팩을 만든다. 이해가 안 되면 코드를 보는게 나을 수도 있다. 12345678910111..

너 봄에는 캡사이신이 맛있단다 (http://boj.kr/15824) 이 문제는 수학문제에 가까운 것 같다. 우선 최솟값과 최댓값만 정하면 중간에 뭐가 들어가던 상관이 없다는 아이디어를 떠올려야 한다. 즉, 정렬한 뒤에 양쪽에 두 원소를 고른 뒤 사이에 있는 원소는 들어가던 말던 주헌고통지수는 달라지지 않는다.우선 그냥 식을 세워봤다. $A_i$는 $i$번째로 스코빌지수가 작은 메뉴다. $2^{n-2}(A_n-A_1)+2^{n-3}(A_{n-1}-A_1)+\cdots+2^{0}(A_2-A_1)$ $+2^{n-3}(A_n-A_2)+2^{n-4}(A_{n-1}-A_2)+\cdots+2^{0}(A_3-A_2)$ $+\cdots$ $+2^0(A_n-A_{n-1})$각 행에서 계속 빼는 메뉴..

놀이기구1 (http://boj.kr/14434) 먼저, 날짜별로 구하는건 필연적으로 놀이기구들을 다 확인해야 돼서 힘들다고 생각했다. 그래서 놀이기구별로 언제부터 가능한지를 이분탐색으로 찾으려 했는데, 어떤 날에 두 아이의 키가 얼마인지를 바로 알려면 $NK$크기의 공간이 필요해서 필요한 것만 남기는 방법을 고민했다. 이 부분은 금방 알아냈다. 각 아이별로 키가 크는 시점만 저장해논 뒤, 이분탐색으로 현재 시점이 각 아이의 몇 번째 성장인지를 찾으면 된다. 이렇게 놀이기구가 가능한 날을 구한 뒤, 그 날의 카운트를 늘려주면 앞에서부터 답을 셀 수 있다풀고나서 찾아보니 parallel binary search라는 기법이였다. 유성문제와 비교했을때 이 풀이가 pbs라고 하기엔 이상한 것 같다... 12..

기념품 (http://boj.kr/12873) 링크드리스트를 이용해 $t^3$만큼 뒤로 가서 지워도 되지만, 점화식을 찾을 수 있다.$n$명이 있을 때는 $1^3$번째 사람이 제외된다. 그 후에, $n-1$명이 남았을 때 아까 제외된 사람부터 출발한다. 즉, $n$명이 있을 때의 결과는 $n-1$명이 있을 때 $1$번부터 시작한 결과와 같다. 마찬가지로 $n-1$명이 있을때의 결과는 $n-2$명이 있을 때 $1^3+2^3$번부터 시작한 결과이다.식으로 나타내면, $i$명이 있을 때의 결과를 $D_i$라고 했을 때, $D_1=1,$ $D_i = (D_{i-1} + (n-i+1)^3 - 1) \bmod i + 1$이다.식이 좀 복잡해보이는데, $-1$과 ..

의좋은 형제 (http://boj.kr/2499) 만약 $i$번째 열까지에서 합으로 $k$를 만들 수 있다면, $i+1$번째 열에서 $k$에 다음 열의 수를 더한 것도 만들 수 있다. 문제에서 합이 40000을 넘을 일이 없기 때문에, dp로 찾을 수 있다. 앞의 열의 높이가 현재보다 작아야거나 같아야한다는 점에 유의해서 잘 구현하면 된다. 형을 기준으로 했더니, n번째 행부터 시작해서 매우 헷갈린다.마지막에 높이를 찾는 방법은, 가장 오른쪽 열부터 답이 되는 높이만큼의 합을 빼주면서 찾으면 된다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546#include using namespace ..