klimmek55

성벽 (http://boj.kr/10717) 일본어 풀이가 있다.왼쪽 위 꼭짓점을 기준으로 오른쪽 아래 꼭짓점을 찾는다고 생각해보자. 전체적으로 대각선 형태로 찾게 된다. 기준점에서 오른쪽 아래 점이 적어도 $L-1$만큼은 떨어져야 하고, 오른쪽으로 뻗어나갔을 때 최대 거리와 아래로 뻗어나갔을 때 최대 거리의 최솟값이 가능할만한 범위다. 다시말해 $[L-1~,\text{(뻗어나갈 수 있는 거리)}]$가 확인해야할 범위다.답이 되는 점들은 범위 안에 포함되는 점들 중에서 찾아야 한다. 이 점들은 왼쪽과 위로 뻗었을 때 최대 거리 중에 작은 것 만큼까지만 답이 될 수 있다.그럼 이 점들을 찾는 시간을 줄여보자. 우선 상하좌우로 뻗는 거리는 DP로 구할 수 있다. 그리고 답을 찾을 때 범위 내의 합을 ..

N포커 (http://boj.kr/16565) 카드가 13종류밖에 안 되니 포함배제의 원리로 구해보자. 구해야 하는 것은 한 종류라도 $4$가지가 모인 경우이다. 이는 한 종류를 $4$가지 모은 경우 - 두 종류를 $4$가지 모은 경우 + 세 종류를 $4$가지 모은 경우 - 네 종류를 $4$가지 모은 경우 + ... 이다. 즉 홀수개를 모은 경우의 수는 더해주고 짝수개를 모은 경우의 수는 빼주면 된다. $n$개를 뽑아 $i$종류를 $4$가지 모은 경우의 수는 조합으로 생각해 볼 수 있다. 카드 $4i$개는 모아야하니 정해진 부분이고, $4i$개를 제외한 나머지 $n-4i$개는 아무렇게나 들어가도 된다. 정해진 부분은 $13$종류의 카드 중 $i$개를 고르는 ..

하와와 대학생쨩 하와이로 가는 거시와요~ (http://boj.kr/16456) 언뜻 보면 주어진 3가지 동작으로 바로 탐색을 할 수 있을 것 같지만, 한 칸 전으로 돌아가는 동작때문에 처리하기가 힘들다. 이 전으로 돌아가는 동작만 잘 처리하면 dp식을 찾을 수 있다.일단 한 칸 전으로 돌아가려면 돌아갈 칸은 방문한 적이 없어야 하기 때문에 무조건 2칸 이동한 후에 1칸 돌아오는 이동이 묶일 수 밖에 없다. 마찬가지로 한 칸 전으로 돌아갔으면 현재 칸, 다음 칸은 이미 방문했기 때문에 2칸을 이동할 수 밖에 없다. 즉, (+2) -> (-1) -> (+2) 는 하나의 이동이라고 볼 수 있다. 그러면 이제 식을 세우는 일은 간단하다. $D_i$를 $i$번째 섬까지 모두 방문하는 경우의 수라고 한다...

Pictures with Kittens (easy version) (http://codeforces.com/problemset/problem/1077/F1) Pictures with Kittens (hard version) (http://codeforces.com/problemset/problem/1077/F2) 난이도가 easy가 2100, hard가 2300인데 사실 그 정도는 아닌 것 같다. Div3 마지막 문제들이었는데 내 힘으로 풀어서 조금 뿌듯하다. 근데 대회에서 푼 건 아니라서 조금 아깝다. 이런 dp 최적화는 간단하고 충분히 또 나올만 해서 풀이를 적어둬야겠다. easy는 간단하게 dp로 풀 수 있다. 일단 $D_{i,j}$를 $i$번째 사진을 선택하고 총 $j$개를 골랐을 때의..

Codeforces Round #520 (Div. 2) 사실 B번은 너무나도 틀리기 쉬운문제라서 내 것도 당연히 반례가 있을거라고 생각하긴 했다. 그래도 왠만한거 다 해보고 잠근다음에 핵을 하려 했는데... 너무 졸려서 그냥 중간에 잤다. 시스템테스트에서 너무 많이들 틀려서 순위가 크게 바뀌지 않은게 다행이긴 하다. 레이팅이 1814에서 1825로 11점 올랐는데, B번을 맞았으면 50점은 올랐을 것 같은데 조금 아쉽다. 다시 떨어지더라도 보라색 달고싶은데... A. A Prank 증가하는 수열에서 다시 복구할 수 있도록 원소들을 지우라는건데, 당연히 1씩 증가하는 부분의 길이를 구하면 된다. 문제는 복구할 때 원소들이 1부터 1000사이라는 점인데, 수열 양 옆에 1과 1000을 넣어두면 깔끔하게 처리..

수열의 값 (http://boj.kr/2867) 최댓값과 최솟값은 별개다. 즉, 모든 부분수열에서 최댓값의 합 - 최솟값의 합을 구하면 되는 문제다. 주어진 수열을 $a$라고 하자. 그리고 현재 보고 있는게 $i$번쨰 항이라는건 $i$번째 항으로 끝나는 부분수열만 보겠다는 뜻이라고 하자. 우선 최댓값과 최솟값은 같은 방법으로 구할 수 있을테니 최댓값만 생각해보자. $a_i$가 $1\sim i$번째 항까지의 최댓값이라고 해보자. 그렇다면 $a_i$로 끝나는 부분수열은 항상 $a_i$가 최댓값일 수밖에 없다. $a_{i-2}$가 $1\sim i$번째 항까지의 최댓값이고, $a_i$가 그 이후의 최댓값이라고 해보자. 그렇다면 $a_i$로 끝나는 부분수열 중 $i-2$..

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라는걸..