본문 바로가기

알고리즘/Dynamic Programming15

[DP] 백준 11058 : 크리보드 - 파이썬 Python https://www.acmicpc.net/problem/11058 11058번: 크리보드 N = 3인 경우에 A, A, A를 눌러 A 3개를 출력할 수 있다. N = 7인 경우에는 A, A, A, Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V를 눌러 9개를 출력할 수 있다. N = 11인 경우에는 A, A, A, Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V, Ctrl-A, Ctrl-C, Ctrl www.acmicpc.net 생각하기 dp[N]을 N번 키보드를 눌렀을 때, 화면에 출력할 수 있는 A의 최대 개수라고 한다 먼저 각 버튼의 종류를 살펴보자면 A를 추가 출력하기 위해 한번 누르면 된다 ctrl + A, ctrl + C는 출력을 위한 것이 아니라 ctrl + V의 선행 조건이.. 2022. 3. 16.
[DP] 백준 12869번 : 뮤탈리스트 - 파이썬 Python https://www.acmicpc.net/problem/12869 12869번: 뮤탈리스크 1, 3, 2 순서대로 공격을 하면, 남은 체력은 (12-9, 10-1, 4-3) = (3, 9, 1)이다. 2, 1, 3 순서대로 공격을 하면, 남은 체력은 (0, 0, 0)이다. www.acmicpc.net DP문제는 내가 제일 어려워하는 유형이라 이 문제는 풀지 못하였다 백준 강의 앞부분에서 힌트를 얻고 풀어본 것을 써본다 생각하기 SCV의 값은 3이하로 매우 작다 각각의 SCV는 체력을 가지고 있다. DP[i][j][k] - SCV의 체력이 i, j, k 일때 모두 파괴하는 최소 공격횟수 SCV가 3마리라고 가정으로 하고 만약 2마리인 경우에는 DP[i][j][0]으로 처리해주면 된다 따라서 3차원 DP를.. 2022. 2. 16.
[DP] 백준 1496번 : 기타리스트 - 파이썬 Python https://www.acmicpc.net/problem/1495 1495번: 기타리스트 첫째 줄에 N, S, M이 주어진다. (1 ≤ N ≤ 50, 1 ≤ M ≤ 1,000, 0 ≤ S ≤ M) 둘째 줄에는 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이가 주어진다. 이 값은 1보다 크거나 같고, M보다 작거나 같다. www.acmicpc.net 생각하기 N개의 연주곡 매번 곡이 시작하기 전에 볼륨을 바꾸고 연주 V[i] - i번째 곡을 연주하기 전에 바꿀 수 있는 볼륨 (차이) -> P + V[i] 혹은 P - V[i] 로 연주 가능 이때, 0 2022. 2. 4.
[DP] 백준 11066번 : 파일 합치기 - Python 파이썬 https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net 생각하기 파일을 합치는데 연속된 파일들을 합치는 것이 포인트였다 1 2 3 4 의 파일들이 있다면 1 (2,3,4) (1, 2) (3, 4) 1, 2, 3) 4 -> 3가지의 경우 중에서 작은 합치는 비용을 찾으면 된다 결국 작은 문제들이 합쳐져서 큰 문제의 답을 이루는 DP를 사용하면 된다는 것을 알았다 점화식을 세워보면 dp[i][j] 는 i번째 data 부터 j번째 data까지 합치.. 2022. 1. 21.

티스토리툴바