DP8 [백준] 2011: 암호코드 - 한 자리와 두 자리 해석을 더하는 DP (Java) 문제 바로가기숫자를 어디에서 나눌지가 경우의 수를 만든다알파벳 A부터 Z까지를 1부터 26에 대응시킨다. 숫자 문자열이 주어졌을 때 이를 알파벳으로 해석하는 방법의 수를 구해야 한다.예를 들어 121은 다음 세 가지로 해석할 수 있다.1 / 2 / 1 → A B A12 / 1 → L A1 / 21 → A U각 위치에서 마지막 숫자 한 자리를 독립된 문자로 볼 수도 있고, 마지막 두 자리를 하나의 문자로 볼 수도 있다.처음에는 0이 나올 때마다 별도 분기를 만들어 처리했다. 하지만 상태를 “앞에서부터 i자리까지 해석하는 방법의 수”로 정의하면 한 자리와 두 자리 조건을 독립적으로 검사해 같은 점화식으로 처리할 수 있다.dp는 앞에서부터 해석한 경우의 수다다음과 같이 상태를 정의했다.dp[i.. 2024. 5. 14. [백준] 1915: 가장 큰 정사각형 - 세 방향을 확인하는 2차원 DP (Java) 문제 바로가기모든 정사각형을 직접 확장하지 않는다0과 1로 이루어진 배열에서 값이 모두 1인 가장 큰 정사각형의 넓이를 구해야 한다.각 칸을 정사각형의 시작점으로 정하고 크기를 하나씩 늘리며 내부가 모두 1인지 확인할 수 있다. 하지만 같은 영역을 여러 번 검사하게 되고, 정사각형이 커질수록 확인할 칸도 많아진다.나는 현재 칸에서 끝나는 정사각형의 크기를 이전에 계산한 주변 값으로 구하는 DP를 사용했다.핵심은 현재 칸에 1이 있는지만 보는 것이 아니라, 현재 칸을 오른쪽 아래 꼭짓점으로 삼았을 때 왼쪽 위 방향으로 얼마나 큰 정사각형을 만들 수 있는지 저장하는 것이다.dp에 정사각형의 한 변 길이를 저장한다DP 상태를 다음과 같이 정의했다.dp[i][j]= (i, j)를 오른쪽 아래 꼭짓점으로 하는 .. 2024. 5. 14. [백준] 11066: 파일 합치기 - 누적합과 구간 DP로 최소 비용 구하기 (Java) 문제 바로가기파일을 합치는 순서에 따라 총비용이 달라진다여러 파일을 순서대로 하나의 파일로 합칠 때 필요한 최소 비용을 구해야 한다. 인접한 파일이나 이미 합쳐진 연속 구간끼리 합칠 수 있고, 두 파일을 합치는 비용은 두 파일 크기의 합이다.예를 들어 크기가 40, 30, 30인 파일이 있다고 하자.앞의 두 파일을 먼저 합치면 다음과 같다.40 + 30 = 7070 + 30 = 100총비용 = 70 + 100 = 170뒤의 두 파일을 먼저 합치면 비용이 달라진다.30 + 30 = 6040 + 60 = 100총비용 = 60 + 100 = 160최종 파일의 크기는 어느 순서로 합쳐도 100이다. 하지만 중간 파일을 만들 때 낸 비용까지 누적되므로 총비용은 달라진다.처음에는 크기가 작은 파일부터 합치면 될 것.. 2024. 5. 14. [백준] 11049: 행렬 곱셈 순서 - 구간 DP로 최소 연산 횟수 구하기 (Java) 문제 바로가기곱셈 순서에 따라 연산 횟수가 달라진다여러 행렬을 입력된 순서대로 모두 곱할 때 필요한 곱셈 연산의 최솟값을 구해야 한다. 행렬의 순서를 바꿀 수는 없지만, 괄호를 묶는 위치는 바꿀 수 있다.크기가 A × B인 행렬과 B × C인 행렬을 곱하려면 다음 횟수의 연산이 필요하다.A × B × C예를 들어 세 행렬의 크기가 다음과 같다고 하자.M0: 5 × 3M1: 3 × 2M2: 2 × 6왼쪽부터 곱하는 경우는 다음과 같다.(M0 × M1) × M2M0 × M1: 5 × 3 × 2 = 30결과 행렬: 5 × 2(5 × 2) × M2: 5 × 2 × 6 = 60총 연산 횟수: 90뒤의 두 행렬을 먼저 곱하면 비용이 달라진다.M0 × (M1 × M2)M1 × M2: 3 × 2 × 6 = 36결과 행.. 2024. 5. 14. [백준] 2410: 2의 멱수의 합 - 1의 개수로 경우를 나누는 DP (Java) 문제 바로가기같은 수를 순서만 바꾼 경우는 하나로 센다정수 N을 2의 멱수의 합으로 나타내는 방법의 수를 구해야 한다.사용할 수 있는 수는 다음과 같다.1, 2, 4, 8, 16, ...같은 수를 여러 번 사용할 수 있지만 순서는 구분하지 않는다. 예를 들어 1 + 2와 2 + 1은 같은 방법이다.처음에는 각 멱수를 동전처럼 보고 일반적인 동전 조합 DP를 사용할 수 있다고 생각했다. 하지만 이 문제에서는 2의 멱수라는 규칙을 이용하면 1차원 점화식을 더 간단하게 만들 수 있다.dp[n] = n을 2의 멱수의 합으로 나타내는 방법의 수핵심은 각 표현에 포함된 1의 개수를 기준으로 경우를 나누는 것이다.1이 두 개 이상인 경우어떤 표현에 1이 두 개 이상 들어 있다면 그중 1 두 개를 제거할 수 있다.n의.. 2024. 5. 13. [백준] 23083: 꿀벌 승연이 - 벌집 좌표를 처리하는 메모이제이션 DP (Java) 문제 바로가기벌집에서는 열에 따라 이웃의 좌표가 달라진다벌집 모양의 격자에서 아래쪽, 오른쪽 위, 오른쪽 아래로 이동하며 도착점까지 가는 경로의 수를 구하는 문제다. 구멍이 뚫린 칸은 지나갈 수 없다.나는 오른쪽 위로 이동할 수 있다는 점 때문에 계산 순서를 먼저 고민했다. 일반적인 사각 격자처럼 행을 위에서 아래로 계산하면 아직 계산하지 않은 행의 값이 필요할 수 있었다. 그래서 도착점에서 필요한 이전 칸을 재귀로 찾아가는 Top-down DP를 사용했다.다만 Bottom-up이 불가능한 것은 아니다. 행보다 열을 먼저 처리하면 이전 열을 완성한 뒤 현재 열을 계산할 수 있다. 이 차이는 뒤에서 다시 정리한다.DP는 현재 칸까지 도착하는 경로 수다배열의 의미를 다음과 같이 정했다.dp[r][c]= (1.. 2024. 5. 12. [백준] 1535: 안녕 - 체력 99를 한도로 푸는 0/1 배낭 DP (Java) https://www.acmicpc.net/problem/1535시작 체력은 100이지만 사용할 수 있는 체력은 99다사람마다 인사할 때 잃는 체력과 얻는 기쁨이 정해져 있다. 각 사람에게 최대 한 번 인사할 수 있고, 체력이 0 이하가 되지 않는 범위에서 기쁨의 합을 최대화해야 한다.나는 사람을 하나씩 보면서 인사하는 경우와 하지 않는 경우를 비교하는 2차원 DP로 풀었다. 여기서 먼저 정리할 조건은 체력을 100까지 써도 되는 것이 아니라 99까지만 쓸 수 있다는 점이다.남은 체력 = 100 - 사용한 체력남은 체력 > 0따라서 사용한 체력 ≤ 99배열의 두 번째 크기를 100으로 만들면 인덱스는 0부터 99까지다. 최종 답을 dp[N][99]에서 읽는 것도 이 조건 때문이다.사람 한 명을 물건 하나.. 2024. 5. 12. [백준] 2624: 동전 바꿔주기 - 개수 제한이 있는 동전 조합 DP (Java) https://www.acmicpc.net/problem/2624동전의 금액뿐 아니라 개수도 제한되어 있다동전의 금액과 종류별 개수가 주어질 때, T원을 만드는 방법의 수를 구하는 문제다. 같은 구성이라면 동전을 꺼내는 순서가 달라도 하나의 방법으로 센다.나는 동전 개수가 정해져 있다는 점이 어려웠다. 금액만 맞추는 것으로는 부족하고, 각 종류를 주어진 개수 안에서 사용해야 했다. 그래서 이전 동전 종류들로 만든 결과와 현재 종류까지 추가한 결과를 분리하는 2차원 DP로 구현했다.현재 종류의 동전을 몇 개 사용할지 먼저 정하고, 남은 금액을 이전 종류들로 만드는 경우의 수를 더하는 방식이다.DP의 두 번째 인덱스는 동전 개수가 아니라 종류 수다dp[amount][i]= 앞의 i가지 동전만 사용해서 amo.. 2024. 5. 12. 이전 1 다음