klimmek55

Cloud Computing (http://codeforces.com/problemset/problem/1070/C) $1\sim n$번 칸에서 각각 최대 $k$개의 코어를 사야 하는데, 당연히 살 수 있는 코어 중에서 가격이 싼 것 부터 차례대로 사는게 이득이다. 그렇다고 계획들을 정렬한 뒤 싼 것부터 하나하나 추가해가다보면, 어떤 칸에서 코어를 $k$개 넘게 샀는지를 확인하기 힘들다. 그래서 계획별로 보지 않고, 칸 별로 어떤 계획을 사용할지를 확인해야한다.현재 $i$번째 칸에서 적용할 계획을 확인하고 있다면, 구간에 $i$가 포함되는 계획들을 찾아야 한다. 어차피 $1$번째 칸부터 $n$번째 칸까지 차례대로 볼 것이므로, $i$가 계획의 시작점일 때 계획 후보에 넣고, ..

불끄기 (http://boj.kr/1819) $T$의 제한이 작다는 부분에서 힌트를 얻었다.우선 버튼의 순서는 중요하지 않다는 것은 당연하고, 같은 버튼을 두 번 이상 사용할 필요가 없다는 것도 당연하다.그러면 이제 왼쪽부터 차례대로 이 버튼을 사용할지 말지를 결정하면 되는데, 이 부분을 DP로 결정한다. 여러 방법이 있겠지만, $D_{ij}$를 $i$번째 전구부터 $T$개의 상태가 $j$일 때, $i$번째 전까지 켜진 불의 개수로 정했다. (왜냐면, $i$번째 전구의 앞은 더 이상 바꿀 일이 없고, 앞으로 $T$개는 현재 영향을 미치는 범위다.) $j$는 비트를 이용해 나타낼 수 있고, 버튼의 순서는 버튼을 눌렀을 때마다 기록해둬서 찾으면 된다.비트를 사용하는 DP라는걸..

재미있는 박스 정리 (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$번째 수로 넘어온다면 \(..

직사각형의 개수 (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$열을 청소하게 될 것이다. ..