재미있는 박스 정리 (http://boj.kr/12945) 이 문제도 매우 오래 고민했다. 일단 오름차순으로 정렬한다. 그 뒤에 작은 것부터 차례대로 보는데, 현재 알아야하는 정보는 두 가지다. 하나는 현재 상자가 넣을 수 있는 상자 개수이고, 하나는 이전의 상자 중에서 다른 상자에 넣을 수 있는 상자의 최댓값이다. 그럼 최댓값 * 2만큼은 이미 정해진 상자이다. 정해진 상자에서 다른 상자에 들어가는 상자는 작을 수록 좋다. (다른 상자를 넣을 필요가 없으니까) 그리고 다른 상자를 넣는 상자는 클 수록 좋다. (현재 상자가 작은 상자를 넣을 수도 있으니까) 그러니 두 개를 고려해서 현재 상자가 넣을만한 상자가 남았는지를 보면 된다.생각해보니 이분탐색으로도 될 것 같다. 1234567891011121314..
노래방 (http://boj.kr/12932) 한 2주 동안 고민해서 풀었는데, 사실 간단한 방법이라서 허무했다. 영선이와 효빈이가 각자 뭘 고를지를 정할 필요 없이, 마지막에 골라진 두 수만 알고 있으면 된다. \(D[i][j]\)를 \(i\)번째 수와 \(j\)번째 수가 마지막 수일 때 최소 난이도라고 정한다. 그러면 경우는 3가지가 있다. 영선이가 쭉 골라오다가 효빈이가 지금 처음 고르는 것이라면 \(D[i][i-1]\)는 현재까지의 난이도 총합이 된다. 그리고 \(i-1\)번째 수와 \(j\)번째 수가 마지막인 경우, \(D[i-1][j]\)에서 \(i-1\)번째 수에서 \(i\)번째 수로 넘어온다면 \(D[i][j]\)를 갱신할 수 있고, \(j\)번째 수에서 \(i\)번째 수로 넘어온다면 \(..
Educational Codeforces Round 50 (Rated for Div. 2) 후기
Educational Codeforces Round 50 (Rated for Div. 2) A. Function height 문제 설명도 길고 그래프까지 나와있어서 무서웠는데, 해석만 하면 간단하다. 어떤 점의 높이를 1올리는 것은 넓이를 1올리는 것과 같다. 그러니 점들에 넓이를 나눠준다고 생각하면 된다.12345678910#include int main() { long long n, k; scanf("%lld %lld", &n, &k); printf("%lld", (n + k - 1) / n); return 0;}Colored by Color Scriptercs B. Diagonal Walking v.2 우선 \(k\)보다 큰 좌표에는 도달할 수 없다. 그리고, \(x\)좌표와 \(y\)좌표 모두 마..
Manthan, Codefest 18 (rated, Div. 1 + Div. 2) 후기
Manthan, Codefest 18 (rated, Div. 1 + Div. 2) A. Packets 영어가 안 돼서 문제를 이해하느라 힘들었다. 문제 내용은, 동전의 총합이 \(n\)이 되고, 그 중 몇개를 뽑아 합으로 \(1\)부터 \(n\)까지의 수를 모두 만들 수 있게 하는 동전의 최소 개수를 구하는 것이다. 동전을 선택하는 것을 비트로 생각하면, 이진수로 나타내는 것이 가장 효율적이므로 가까운 2의 제곱수를 찾으면 된다. 이해 못 하고 한 번 제출해서 틀렸었다.1234567891011121314#include int main() { long long n; scanf("%lld", &n); for (long long i = 1, cnt = 1;true;i *= 2, cnt++) if (i > n)..
직사각형의 개수 (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 범위도 넘어갈 수 ..