전체 글 (32) 썸네일형 리스트형 재밌었던 DP 모음 - 4, 심심풀이 문제 P4. 재우의 카드깡https://www.acmicpc.net/problem/28693 더보기f(i, j) = i장의 카드가 남았는데 j개의 정보를 이미 알고있을때 시행 기댓값j장의 정보를 알고있으니 당연히 i-j장 중에서 카드를 하나 뽑을 것이다. 1-1.p = j/(i-j)의 확률로 이미 아는친구를 뽑을 것이다.그러면 이미 아는 정보를 활용해서 바로 매치를 시켜버릴테니 기댓값은 p*(f(i-2, j-1)+1)이 된다. 1-2.p = (i-2*j)/(i-j)의 확률로 초면을 뽑을 것이다. 2-1.q = 1/(i-j-1)의 확률로 첫 시행과 같은 친구를 친구를 뽑는다.기댓값은 p*q*(f(i-2, j)+1) 2-2.q = j/(i-j-1)의 확률로 이미 알고 있는 친구를 뽑는다.같은 카드 두 장을 알고있.. 재밌었던 DP 모음 - 3, 심심풀이 문제 P4. 두 팀으로 나누기https://www.acmicpc.net/problem/30896 더보기A가 팀에 속한 사람의 최솟값이 반영된다.A[i]에 대해 정렬해보자. 어떻게 팀을 나누던 반드시 A[1]을 들고 있는 사람이 속한 팀이 존재한다. A를 고정할 것인데, 이미 하나는 고정되어있고그럼 상대팀의 A를 A[j]로 정한다면 일단 상대팀은 j미만의 A[i]를 지닌 친구들을 절대 가질 수 없다. 현재 팀 상황은A[1] * sum(B[1] ~ B[j-1]) / B[j] * A[j] 가 되게 된다. 이제 [j+1 ~ N]의 선수들을 잘 배치해서 최소로 만들어주면 되는데f(i, k) = [i ~ N]의 선수들로 k라는 값을 만들 수 있는가? 라는 함수를 만들어주고 f(j+1, k)가 가능한 경우에 대해서A[1].. 재밌었던 DP 모음 - 2, 심심풀이 문제 https://www.acmicpc.net/problem/24528 엄청 긴 문자열이 주어졌을 때 서로다른 서브시퀀스의 개수를 구하는 문제더보기f(c) = 현재 위치까지 봤을 때 문자 c가 가장 마지막으로 오는 유니크한 서브시퀀스의 개수라고 정의하자.만약 vi가 1이라면f(c) = sum(f(i))+1임을 바로 알 수 있다. 여기에 연산을 한 번 더 적용하면 f(c) = (sum(f(i))+1)*2 - f(c)가 된다.유니크한 문자열 뒤에 c를 이어붙인 뒤, 한 번 더 이어붙이는 것을 반복하면f(c) = (sum(f(i))+1)*vi - f(c)*(vi-1) 임을 알 수 있다.시각적으로 표현해도 쉽게 나옴 https://www.acmicpc.net/problem/17682 격자에서 텐트의 방향과 위치를.. 재밌었던 DP 모음 - 1 https://www.acmicpc.net/problem/30788 그림을 축을 기준으로 뒤집는 문제.더보기일단 n이 홀수면 뭘 해도 거울에 반사된 상태로 보이기때문에 불가능d도인 선으로 그림을 뒤집으면 2*d 만큼 각도를 조정할 수 있다.근데 세계가 뒤바껴있는 상태에서는 -2*d 만큼 작용한다.홀수 인덱스에선 2*d, 짝수 인덱스에선 -2*d를 적용하여 냅색하고 역추적해주자 https://www.acmicpc.net/problem/24099 문자열이 주어지고 문자 u 뒤에 문자 v가 오지 않도록 하는 서브시퀀스의 개수를 구하는 문제 더보기dp(i) = i번 인덱스의 문자를 끄트머리에 사용한 문자열의 개수f(c) = 문자 c를 가장 끄트머리에 사용한 문자열의 개수 dp(i) = sum(f(c))+1 조.. [BOJ] 8158. Blockade https://www.acmicpc.net/problem/8158 문제를 요약하면무방향 연결그래프에서 정점 i와 직접 연결된 간선을 모두 삭제시켰을때u -> v로 갈 수 없는 쌍의 개수를 ans(i)라고 한다.1~n에 대해 ans(i)를 구하여라. 일단 BCC를 돌려준다.정점 X에 파란색 간선을 타고 왔으면빨간 간선들이 브릿지인지만 궁금하다.브릿지면 분할하고 아니면 냅두고쪼개진 애들끼리 곱해주면끗 이전 1 2 3 4 ··· 7 다음
