직사각형의 개수 (http://boj.kr/2171) 가능한 직사각형을 다 셀 필요는 없다. 우선 x좌표가 같은 점들끼리 묶는다. 그리고 묶음들끼리 비교하면서 두 묶음에 y좌표가 같은 점들이 몇 개 있는지를 찾는다. 그러면 각 묶음에서 y좌표가 같은 두 점씩 고르면 직사각형을 만들 수 있으므로, y좌표가 같은 점의 쌍에서 2가지를 고르는 경우와 같다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556#include using namespace std; pair pt[5000];vector sor; int main() { int n; long long ans = 0; sc..
책 페이지 (http://boj.kr/1019) 전에 대충생각했다가 틀려서 묵혀놨는데, 새벽이라 집중이 잘 돼서 결국 풀었다. 푸는 방법은 여러가지가 있겠지만, 나는 일단 N보다 한 자리수 작은 것들을 먼저 셌다. 예를들어 N이 5자리 수라면, 4자리수에서 1~9까지의 숫자는 \(4\times{10^3}\)번 등장한다. (0은 따로 계산했다.)그 뒤에, 현재 수를 본다. 예를들어 N이 1231라고 해보자. 그러면, 0XXX인 경우는 불가능하므로 넘어간다. 10XX인 경우는 1과 0이 \(10^2\)번 등장하고 모든 숫자가 \(2\times{10^1}\)번 등장한다. 11XX인 경우는 1과 1이 \(10^2\)번 등장하고 모든 숫자가 \(2\times{10^1}\)번 등장한다. 120X인 경우는 1과 2와..
유성 (http://boj.kr/8217) 이 문제는 고민을 해봐도 모르겠어서 안 풀려 했는데, 방법을 알아두면 좋을 것 같아서 풀이를 봤다. 일단 기본적으로 구간 업데이트를 펜윅트리로 \(O(\log{n})\)만에 하는 방법은 알고 있어야 한다. 회원국별로 날짜를 이분탐색으로 찾으려고 해도, 그 날에 유성의 개수를 확인하려면 미리 저장해둘 수는 없기 때문에 \(O(k\log{m})\)으로 매번 트리를 만들어야 한다. 그래서 아이디어가 하나 더 들어가서, 어떤 날의 트리를 최대한 활용해야 한다. 그러기 위해 모든 회원국이 하는 이분탐색을 동시에 한다. 즉, 트리가 저장하고 있는 날짜 별로, 그 날에 가능한지 확인해야 하는 회원국들을 같이 확인해주면 된다. 이때 총합이 long long 범위도 넘어갈 수 ..
돌맹이 제거 (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})\)각 행에서 계속 빼는 메뉴..