본문 바로가기
728x90

다이나믹 프로그래밍17

[python] 백준 2643 색종이 올려 놓기 https://www.acmicpc.net/problem/2643 2643번: 색종이 올려 놓기 첫 번째 줄에는 색종이의 장수가 주어진다. 다음 줄부터 각 줄에 색종이의 두 변의 길이가 주어진다. 두 변의 길이는 한 칸 띄어 주어진다. 색종이의 최대 장수는 100이고, 각 변의 길이는 1000보다 www.acmicpc.net 문제 해결 작은 것부터 쌓아 올려서 최대한 많이 쌓을 수 있도록 하면 된다. w, h가 구별되지 않으므로 두 변중 긴 변을 w, 작은 변을 h로 정렬한다. 각 색종이를 길이가 큰 것 부터 내림차순으로 정렬한다 하나씩 확인하면서 이전 것들 길이를 비교하면서 w, h 모두 더 길 때 dp[w][h] (가장 큰 색종이의 길이가 w, h일 때 쌓아올릴 수 있는 최대 개수) 를 dp[pw][.. 2024. 4. 8.
[python] 백준 1315 RPG https://www.acmicpc.net/problem/1315 1315번: RPG 준규는 새 RPG 게임을 시작했다. 이 게임에서 캐릭터는 2가지 스탯을 가지고 있다. 하나는 힘(STR)이고, 다른 하나는 지력(INT)이다. 캐릭터를 생성했을 때, 두 스탯은 모두 1이다. 게임에는 총 N개의 www.acmicpc.net 문제 해결 수가 크다는 것에서 우선 다이나믹 프로그래밍(DP)를 생각해 볼 수 있다. (BFS,DFS는 비현실적) 주어진 퀘스트를 수행할 수 있고 수행하였을 때 추가 능력치를 얻는데 이를 어디에 얼만큼 쓸 것인지 그리디 방식으로 알 수 없다. 그렇다고 브루트 포스 방식도 조금 부담스럽다. 그래서 3가지 리스트를 만들어 문제를 해결하는 방법을 생각할 수 있다. DP[i][j]: STR=.. 2024. 3. 11.
[python] 백준 1509 팰린드롬 분할 https://www.acmicpc.net/problem/1509 1509번: 팰린드롬 분할 세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다. 분할의 개수의 최솟값을 출력하 www.acmicpc.net 문제 해결 팰린드롬은 좌우 대칭인 문자열을 의미한다 문자를 하나씩 나누면 무조건 팰린드롬 분할이 된다. 두 개씩 보면서 팰린드롬을 확인하는 것도 어렵지 않다. $O(N)$ 3개 이상일 때는 어떻게 할 수 있을지 어려웠다. 길이를 3부터 L까지 늘려나가면서 $l$ 확인한다. 시작점을 0부터 $L-l$까지 이동하며 잡고 끝점을 시작점.. 2024. 2. 25.
[python] 백준 11055 가장 큰 증가 부분 수열 https://www.acmicpc.net/problem/11055 11055번: 가장 큰 증가 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수 www.acmicpc.net 문제 해결 전통적인 dp문제 dp[n]을 n을 마지막으로 포함하는 부분 증가 수열중 합이 가장 큰 수를 나타낸다고 하자. 이 때 들어가는 수열중 n 이전 마지막 수를 i라 할 때 dp[n] = max(dp[i]+A[n], dp[n])이 될 것이다. 따라서 이 것을 생각하고 풀면 끝 CODE import sys input = sys.stdi.. 2022. 12. 29.
728x90