재밌었던 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)의 확률로 이미 알고 있는 친구를 뽑는다.

같은 카드 두 장을 알고있다는 정보를 전이하고싶지만 쉽지 않다.

어차피 두 장 모두 알고있다면 다음 턴에 반드시 뒤집을테니 그냥 한번 더 썼다고 친다.

기댓값은 p*q*(f(i-2, j)+2)

 

2-3.

q = (i-2*j-2)/(i-j-1)의 확률로 초면을 뽑는다.

기댓값은 p*q*(f(i, j+2)+1)

 

한줄평

그냥 평범한거같은데

 

---

 

P1. Level Up

https://www.acmicpc.net/problem/17956

 

그냥 문제를 보면

f(i, j, k) = i번 퀘스트를 완료했을때 1렙 경험치가 j, 2렙 경험치가 k일 때의 최소시간

으로 두고 풀면 될거같다.

 

근데 그냥 무지성으로 하면 안되는데

s1 = 25, x1 = 25, x2 = 20과 같은 경우를 고려해보자

 

앞에서부터 전이를하면 1번 퀘스트를 1렙경험치에 사용하는 경우

2번 퀘스트를 1번퀘스트와 같이 1렙경험치에 사용을 못한다.

 

근데 2번퀘스트부터 전이를했다치면

2번 퀘스트를 완료했을때 20경험치이므로 아직 렙업을 안해서

1번퀘스트를 1렙경험치에 사용해줄수있다.

 

따라서 i번 퀘스트를 사용하지 않은 상태로 dp를 채운 뒤

마지막에 i번 퀘스트로 이어주려고 하면 O(N^4)이 되어서

아이보리가 와도 못 돌리는 시간복잡도가 나온다.

 

여기서 하나의 관찰이 필요한데,

어차피 오버플로우를 할 수 있다면 x가 큰 것으로 하는 것이 이득이라는 것이다.

 

x1 = 4, x2 = 7, x5 = 6

다음과 같은 1렙 퀘스트로 오버플로우를 일으킨다고 한다.

1렙 경험치통은 11이다.

 

x1, x5, x2 순으로 하면 14인 반면

x1, x2, x5 순으로 하면 쓰지도 못하고 11에서 멈춘다.

 

따라서 x의 오름차순 정렬을 해준 뒤 dp를 한 번 시행하는 것으로

옵티멀을 찾을 수 있게 된다.

 

한줄평

정렬이 킥이었고, 저 관찰을 쓰는 문제가 뭔가 또 있을거같다.

 

---

 

P2. 나의 라임 오렌지 나무

https://www.acmicpc.net/problem/22900

 

우선 간선의 가중치는 의미가 없음을 관찰해야한다.

시작 정점 i에 말이 있다고 가정하자.

 

1. 패배시킬 수 있는 정점이 있는 경우

다시 올라오지 못하게 가중치를 모두 사용하며 해당 서브트리로 보내버릴것이다.

 

2. 패배시킬 수 있는 정점이 없는 경우

이 말은 본인의 패배와 동치이다.

어느 정점으로 보내던 상대는 ㄳ를 외치며 절대 시작 정점 i로 돌려보내주지 않을 것이다.

 

가중치가 의미 없는 것을 알면 단순한 리루팅dp가 된다.

 

한줄평

리루팅 잘짜는법을 아직도 모르겠다.

 

---

 

P5. 카르텔 님 게임

https://www.acmicpc.net/problem/30688

 

A랑 B는 팀이니까 그냥 한 사람이라고 봐도 무방하다.

그러면 A랑 C랑 싸우는건데,

A는 [2, K]개 가져갈수있고 C는 [1, K]개 가져갈수있다.

 

N == K면

A필승이고

 

K+2 < N <= 2K+1도

A필승이다.

C에게 K+1을 줄 수 있기 때문.

 

그러면 이것보다 큰 경우를 봐보자.

A가 어찌어찌 K+1의 리드를 계속 가지고온다고 해보자.

A의 피지컬로 2(K+1)까지 C에게 떠넘겨도

C는 K만큼을 가져가서 K+2로 만들어버린다.

그럼 A는 불공평한 게임에 대해 울분을 토하며 끝이 나겠다.

 

한줄평

팀은 한 사람이라고 생각하고 연산이 다른 두 명이 싸우는거라 생각하면 쉽다.

 

---

 

P1. NAME

https://www.acmicpc.net/problem/31640

 

f(i, j, x) = s의 i, t의 j까지 작성했고, 마지막으로 사용한 문자가 x이다. 라고 정의하자.

이 경우 k <= 1일 때를 풀 수 있다.

 

어차피 문자 x는 관심이 없고 i사용 o x, j사용 o x 만 궁금하므로

x가 들어갈 상태공간은 4개다.

 

해당 공간을 k칸 확보해야하므로

4^k로 내가 이전 k개에 대하여 s or t에 포함된 사용한 문자를 관리할 수 있다.

 

그러면 문자를 하나씩 적는거는 비용이 1씩 증가하니

BFS로 풀 수 있다.

 

한줄평

그냥 상태만 정의하면 그렇게 어려운거같진 않은데 왜높지

 

 

---

 

P3. 색칠 공부

https://www.acmicpc.net/problem/9521

 

함수형그래프이므로

컴포넌트별로 분리하고

각 컴포넌트를 환형 그래프 하나와 선형 그래프 하나로 생각하면

컴포넌트에서의 경우의 수는 환형 그래프의 경우의 수 * (K-1)^선형 그래프 크기

 

크기 N의 환형 그래프에 같은 색이 이웃하지 않도록 K개의 컬러를 칠하는 방법의 수는

검색결과 (K-1)^N + (-1)^N*(K-1)이라고 한다.

솔직히 이건 검색해도 ㅇㅈ아닌가

 

암튼 컴포넌트끼리 다 곱해주면 된다.

 

한줄평

싸이클 검출 구현할줄 몰라서 많이 얼탔다. 좀 풀어야겠다.

 

---

 

P1. K blocks (추천)

https://www.acmicpc.net/problem/11858

 

f(i, j) = i까지 j개의 블럭으로 분할했을때 최솟값으로 정의하자.

f(i, j) = min(f(k, j-1) + max(A[k+1, i]))

위와 같은 식이 나오는데 최적화해보자.

 

저기서 사용하는 k가 그리 많지 않아보인다.

왜냐면 i->k까지 이동하며 최댓값을 계속 갱신할텐데

그러면 의미있는 k가 사용되려면 A[k+1, i-1]에서 최댓값을 가져야한다.

 

그래서 그러한 k를 모노톤하게 관리해줄거다.

현재 스택에는 A[i] < A[k]인 k만 남아있고

그렇지 않은 k는 모두 구간 i와 머지를했다.

왜와이? 어차피 A[i]보다 작으면 그냥 A[i]-A[k]내고 머지하면그만임

이후에는 A[i]가 더 크기때문에 걔네가 유의미한 영향을 못미침

 

이렇게 머지한 f(i, j)가 f(k, j)보다 작으면 A[i] < A[k]라서 얌생이를 쓰긴 했지만

암튼 현재로서는 더 작은 값을 가지고 있는 것이니 스택에 넣어준다.

 

그러면 스택은 A[i]가 작은것, f(i, j)가 작은것 으로 엄격히 유지된다.

 

한줄평

dp에서 전이를 위해 모노톤스택 쓰는거 진짜 자주나오는거같으니 공부 ㄱ.ㄱ