klimmek55

트리 분할 (http://boj.kr/2454) KOI 고등부 3번 문제인데 내 힘으로 풀게 되어서 꽤 뿌듯하다. 문제 이름대로 주어지는 그래프는 트리형태이니 루트를 기준으로 내려간다고 생각해보자. 그 뒤 루트가 $i$번 노드인 서브트리에서의 답을 $A_i$라고 하자. 그리고 그 답에서의 $i$번 노드를 포함하는 경로의 최소 크기를 $B_i$라고 하자. 그러면 이 두 가지를 가지고 DP로 답을 찾을 수 있다.현재 노드가 $u$일 때, $u$가 루트인 서브트리에서 답이 될 수 있는 경우는 3가지가 있다.1. $u$의 자식들의 답은 그대로 두고, 그 상태에서 $u$ 하나만 있는 경로를 추가하는 경우 2. $u$의 자식 중 하나의 경로에 $u$를 추가하는 경우 3. \(u\..

성벽 (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$번째 섬까지 모두 방문하는 경우의 수라고 한다...

수열의 값 (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$..

불끄기 (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$번째 수로 넘어온다면 \(..