본문 바로가기

DP15

[백준] 7579번: 앱 (Java) 1. 문제설명스마트폰의 메모리는 메모리 부족 상태를 방지하기 위해 활성화 되어 있는 앱들 중 몇 개를 선택하여 메모리로부터 삭제하는 과정을 수행한다.(비활성화)현재 N개의 앱이 활성화 되어 있을 때, 앱 $A_i$는 각각 $m_i$ 바이트만큼 메모리를 사용한다. 앱 $A_i$를 비활성화한 후 다시 실행시키면, 추가적으로 드는 비용은 $c_i$ 이다. 새로운 앱을 실행시키면 추가로 $M$ 바이트의 메모리가 필요하고, 현재 활성화 되어 있는 앱 중 몇 개를 비활성화하여 M 바이트 이상의 메모리를 추가로 확보해야 한다.비활성화 했을 경우의 메모리 $M$ 바이트를 확보하는 비용 $c_i$ 의 최소 비용을 구하는 문제이다.시간 제한: 1초메모리 제한: 128MB 2. 접근 방식DP 방법을 사용한다. (Knapsa.. 2024. 10. 1.
[백준] 21941번: 문자열 제거 (Java) 1. 문제설명지우고 싶은 문자열 S와 지울 수 있는 문자열 A1, A2, …, AM이 주어진다. 문자열 Ai 들은 각자 Xi라는 점수를 가진다. 문자열 S를 삭제 연산을 이용하여 모두 제거하려고 한다.삭제 연산 두 가지문자열 S의 부분 문자열 중에 문자열 Ai 가 존재한다면 해당하는 부분을 지우고, Xi 만큼의 점수를 얻는다. (여러 부분 존재해도 한 번만 지운다.)문자열 S에서 문자 하나를 지우고 점수를 1점을 얻을 수 있다.삭제 연산을 이용하여 문자열 S를 지우려고 할 때 얻을 수 있는 최대 점수를 구하는 문제이다.시간 제한: 1초메모리 제한: 512MB 2. 접근 방식DP 방법을 사용한다.문자열 S의 각 위치에 대해 그 위치까지의 최대 점수를 저장하는 1차원 dp 배열을 사용한다.각 위치에서 고려하.. 2024. 10. 1.
[백준] 11048번: 이동하기 (Java) 1. 문제설명NxM 크기의 미로가 있고, 가장 왼쪽 윗 방은 (1, 1), 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 현재 (1, 1)에 있고, (N, M)으로 이동하려고 한다. 준규가 (r, c)에 있으면, (r+1, c), (r, c+1), (r+1, c+1)로 이동할 수 있고, 방문하는 방의 사탕을 모두 가져갈 수 있다. 준규가 가져올 수 있는 사탕의 최댓값을 구하는 문제이다.시간 제한: 1초메모리 제한: 256MB 2. 접근 방식DP 방법을 사용한다.dp 배열(2차원 배열)에 해당 칸까지 이동했을 때 얻을 수 있는 사탕의 최댓값을 저장한다.DP 점화식: 현재 칸에 도달할 수 있는 세 가지 경로(윗칸, 왼쪽칸, 왼쪽 위 칸)에서 가장 많은 사탕을 얻는 경로를 찾는다.도착점(n-1, m-1)에서.. 2024. 9. 24.
[백준] 11726번: 2xn 타일링 (Java) 1. 문제설명2xn 크기의 직사각형을 1x2, 2x1 타일로 채우는 방법의 수를 10,007로 나눈 나머지를 구하는 문제이다.시간 제한: 1초메모리 제한: 256MB 2. 접근 방식`dp[i]`는 `i` 길이의 직사각형을 채우는 방법의 수를 저장한다.`dp[1]`과 `dp[2]`의 초기값을 설정한다.위 그림을 참고하면 `dp[i] = dp[i-1] + dp[i-2]` 점화식을 구할 수 있다.`dp[i]`를 저장할 때 오버플로우 방지를 위해 문제에서 주어지는 10,007로 나눈 값을 저장한다.최종적으로 `dp[n]`을 구한다. 3. 최종 코드import java.io.*;public class Main { public static void main(String[] args) throws IOExcep.. 2024. 8. 29.
[백준] 가장 긴 짝수 연속한 부분 수열 (small) (Java) 1. 문제설명길이가 N인 수열 S가 있고, S는 1 이상인 정수로 이루어져 있다. 수열 S에서 원하는 위치에 있는 수를 골라 최대 K번 삭제할 수 있다. 삭제를 수행 후 수열에서 짝수로 이루어져 있는 연속한 부분 수열 중 가장 긴 길이를 구하는 문제이다.시간 제한: 1초메모리 제한: 1024MB 2. 접근 방식`dp[i][j]`: 수열의 `i` 번째까지의 원소에서 `j` 개의 홀수를 제거했을 때의 가장 긴 짝수 부분 수열의 길이만약 `s[i]`가 짝수일 경우 이전 상태에서 `j` 개의 홀수를 제거한 것과 동일한 상태에서 현재 짝수를 추가하여 길이를 1 증가시킨다⇒ `dp[i][j] = dp[i-1][j] + 1`만약 `s[i]`가 홀수이고,현재 홀수를 제거 가능할 경우 (j > 0) 이전 상태에서 `j-.. 2024. 8. 28.
[백준] 1463번: 1로 만들기 (Java) 1. 문제설명정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.X가 3으로 나누어 떨어지면, 3으로 나눈다.X가 2로 나누어 떨어지면, 2로 나눈다.1을 뺀다.정수 N이 주어졌을 때, 위의 연산 세 개를 적절히 사용해서 1을 만들려고 한다.연산을 사용하는 횟수의 최솟값을 구하는 문제이다.시간 제한: 0.15초메모리 제한: 128MB 2. 접근 방식`dp[i]`에 i를 1로 만드는데 필요한 소 연산 횟수를 저장한다.점화식을 계산한다.`dp[2]`, `dp[3]`은 각각 1로 초기화 한다.`dp[i]`는 기본적으로 `dp[i-1] +1`로 초기화 한다. (1을 빼는 연산)i가 2의 배수이면, `dp[i]`는 `dp[i/2] + 1`과 비교하여 더 작은 값을 선택한다.i가 3의 배수이면, `dp[i.. 2024. 8. 28.
[백준] 2839번: 설탕 배달 (Java) 1. 문제설명상근이는 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕을 담는 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다. 최대한 적은 봉지를 들고 가려고 한다.시간 제한: 1초메모리 제한: 128MB 2. 접근 방식`dp[i]`를 설탕 무게가 `i`일 때 필요한 최소 봉지 개수를 저장한다.`dp[1] ~ dp[5]` 에 초기값을 설정한다.`i=6` 부터는 `dp[i-3]`과 `dp[i-5]`의 값을 고려하여 계산한다.한 쪽만 0이 아닌 경우: 0이 아닌 값 + 1두 쪽 모두 0이 아닌 경우: `Math.min(dp[i-3], dp[i-5]) + 1`모두 0인 경우: 0으로 설정최종적으로 `dp[n]`이 0이면 -1을 출력, 아니면 dp[n]값을 출력한다. 3. 최종 코드import ja.. 2024. 8. 28.
반응형