klimmek55

카드놀이(https://www.acmicpc.net/problem/2066) 어떤 상태까지 도달할 확률이 $p$이고, 이 상태에서 고를 수 있는 방법이 $N$개가 있다면, 다음 상태로 넘어갈 확률은 $\frac{p}{N}$다.문제는 구현하는 방법이다. 상태는 카드가 그룹별로 $0$개부터 $4$개까지 있을 수 있으니 $5^9$개가 있는데, 모든 상태를 확인하면서 또 DP처럼 구하려면 순서가 중요하니 9중 반복문을 써야한다.하지만 그러면 코드가 복잡해지니, 남은 카드의 수의 합은 항상 순서가 있다는 점에서 BFS로 구현했다.상태도 9차원 배열로 만들어두면 코드가 복잡해지니 map을 사용했다. 12345678910111213141516171819202122232425262728293031..

도로 정비하기 (http://boj.kr/1739) 각 가로도로와 세로도로를 하나의 변수로 생각한다. $i$번 가로도로를 $W_i$, $i$번 세로도로를 $H_i$라고 할 때, 이 도로들이 가질 수 있는 방향은 두 가지이므로 참과 거짓의 불리언 값을 가진다고 생각할 수 있다.버스가 $(W_i,H_i)$에서 $(W_j,H_j)$로 운행한다 했을 때, 가장 간단한 경우인 \(W_i

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

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$개를 골랐을 때의..

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