백준/DP (67) 썸네일형 리스트형 [USACO] 백준 5945 - Treasure Chest 참고이 문제는 "동적계획법으로 푸는 게임이론" 문제이다. 이 키워드에 대해 잘 모르고 있다면 2040 - 수 게임 문제에 대한 풀이를 보고 오는 것이 이해에 도움이 된다. 링크 - https://nicotina04.tistory.com/272 백준 2040 - 수 게임https://www.acmicpc.net/problem/2040 이 문제는 대단히 교육적인 문제이므로 꼭 공부하는 것을 추천한다. 게임 전략 A와 B 둘 다 최적으로 플레이를 한다고 했다. 이를 수식으로 표현하면 어떻게 될까? A의nicotina04.tistory.com풀이두 명의 플레이어가 점수를 먹는 게임을 하므로 $max(First - Second)$를 구하는 문제가 된다. 게임 규칙은 단순하므로 $max(First - Second).. 백준 12199 - Password Attacker (Large) https://www.acmicpc.net/problem/12199 문제의 조건을 만족하는 비밀번호의 갯수를 구하기 위해 다음 점화식을 고려할 수 있다. dp(i, j) := 입력할 수 있는 문자가 i개 남았고 아직 쓰지 않은 키가 j개 남았을 때 최적해 문제에서 j개의 키를 반드시 사용하라고 했으므로 j가 0이 되는 방법을 동적 계획법으로 계산하면 문제의 정답을 구할 수 있다. 백준 23280 - 엔토피아의 기억 강화 https://www.acmicpc.net/problem/23280 다음 점화식을 정의하자.$dp(i, j, k) := $ $i$번째 순서에서 왼손이 $j$, 오른손이 $k$에 있을 때 최적해번호는 총 12개가 있으므로 약 10001 × 12 × 12 크기의 메모리를 사용하여 동적 계획법을 시행할 수 있다.처음에 왼손과 오른손이 각각 번호 1, 3에 있다고 했으므로 $dp(0, 0, 2)$부터 메모이제이션을 하여 정답을 계산할 수 있다.정답 코드 - C++12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364#pragma GCC target("fm.. 백준 32250 - Super Shy (Easy) https://www.acmicpc.net/problem/32250힌트 1더보기만약 먼저 앉은 사람이 아무도 없을 경우 아무 자리에나 앉을 수 있다. 이 조건이 대단히 중요하다.힌트 2더보기최초로 사람을 배치한 이후, 규칙에 따라 사람을 배치하는데 나타나는 성질을 찾을 수 있는가?풀이더보기먼저 사람을 아무 곳에 배치한다고 해보자. 그러면 그 사람을 기준으로 나눈 왼쪽 구간과 오른쪽 구간 $L$과 $R$을 얻을 수 있다. $L$과 $R$에서 사람을 배치할 때는 문제의 규칙에 의해 다음과 같은 성질을 발견할 수 있다. 구간 $L, R$에서 첫 번째 사람이 놓인 기준점을 포함하여 각 사람과의 거리는 2 또는 3이다. 이는 거리를 가능한한 멀리 떨어트려야 한다는 조건을 만족시키기 위해 중앙에 배치하면서 다시 두.. 백준 1398 - 동전 문제 https://www.acmicpc.net/problem/1398 1398번: 동전 문제첫째 줄에 테스트 케이스의 개수 T가 주어진다. 둘째 줄부터 T개의 줄에 초콜릿의 가격이 주어진다. 가격의 1015보다 작거나 같은 자연수이다.www.acmicpc.net 힌트 1더보기동전 교환 문제를 그리디 하게 풀려면 주어진 동전들의 값이 서로 서로소가 아니어야 함이 알려져 있다. 일단 적당한 범위 안에서의 답을 dp로 모두 구해놓고 dp로 도출한 해와 그리디로 푼 해의 차이를 비교해 보자. 유의미한 결과를 얻을 수 있는가?힌트 2더보기30, 40, 80, 90 해설더보기적당히 큰 범위 내에서 dp로 해를 찾은 뒤 그리디하게 구한 해와 비교해보자. 그러면 다음 사실을 발견할 수 있다. 해당 문제의 답을 $f(x).. 이전 1 2 3 4 ··· 14 다음
