다이나믹 프로그래밍 적용단계
1. 최적해의 구조와 특징을 찾는다.
2. 최적해의 값을 재귀적으로 정의한다.
3. 최적해의 값을 계산한다.
4. 계산된 정보들로부터 최적해를 구성한다.
2. 최적해의 값을 재귀적으로 정의한다.
3. 최적해의 값을 계산한다.
4. 계산된 정보들로부터 최적해를 구성한다.
BOJ 1006 - 습격자 초라기
문제 : https://www.acmicpc.net/problem/1006 DP[i][j] : i 번째 열, j타입일 때 남은 열을 적절히 놓아서 만들 수 있는 최소 침투 소대수라고 정의하고 다이나믹 프로그래밍으로 풀면 된다. 이 문제에서 까다로운 점은 구역이 원형으로 연결돼 있다는 점인데, 이는 처음과 끝에 이미 몇개의 소대를 보내 놨다고 생각 (이러면 선형구조로 생각할 수 있음) 하고, 그 경우에 대해 모두 돌려보면 된다. 길이 N에 처음과 끝을 가정하는 경우의 수는 상수번 이므로 O(N)에 풀린다. 코드 : http://ideone.com/XPpr2X 비슷한 문제 (이 문제를 푸는데 동원된 아이디어와 비슷한) : https://www.acmicpc.net/problem/9465 https://www.acmicpc.net/problem/2133 https://www.acmicpc.net/problem/2482 https://www.acmicpc.net/problem/4017
댓글
댓글 쓰기