본문 바로가기
728x90

다이나믹 프로그래밍18

[python] 백준 16287 Parcel https://www.acmicpc.net/problem/16287   문제 해결오직 4개를 쓰며 정확히 w의 무게를 맞추는 방법에 대해서 여러가지 방법을 생각해 볼 수 있다.DP, DFS ...무게가 엄청 클 수 있고 n이 상대적으로 작으므로 n개에서 4개를 고르는 것을 사용한다.그런데 4개를 고를 때 graph를 사용하여 dp를 만들기는 상당히 부담스럽다. 4차원 공간보다 2개씩 나누어 2차원 DP를 만들고 2차원 + 2차원 계산을 하는 것이 좋을 것이라 생각했다.하지만 dp[i][j] 의 value 값을 무엇을 쓸지 사실 의미가 크게 없었다. {0, 1}로 하고 (w-i-j )숫자가 나오는 조합을 N개 안에서 또 찾는 것은 시간복잡도가 상당했다.따라서 dp를 1차원으로 만들어서 확인을 하는 것이 좋.. 2024. 6. 22.
[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.
728x90