목록백준/Dynamic Programming (32)
mojo's Blog
[백준 11049] 행렬 곱셈 순서
문제 링크 => 11049번: 행렬 곱셈 순서 (acmicpc.net) 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net 다이나믹 프로그래밍 문제이다. 많은 분들이 푼 문제이다 보니 꽤 유명한 문제인 것 같다. 이 문제는 행렬의 곱셈 연산 횟수의 최솟값을 찾는 문제이다. 이 문제를 base case와 그렇지 않은 경우를 함수 dp(int start, int end) 를 통해 먼저 살펴보도록 한다. (ABC 행렬이 있다고 가정할 때 start = 0, end = 2 를 의미함) 일단 memoziatio..
[백준 2201] 이친수 찾기
문제 링크 => 2201번: 이친수 찾기 (acmicpc.net) 2201번: 이친수 찾기 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 들 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 다이나믹 프로그래밍 문제이다. 이친수는 다음과 같은 성질을 갖는다고 한다. 이친수는 0으로 시작하지 않는다. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다. 예를 들어서 1, 10, 100, 101, 1000, 1001, 1010, 10000, ... 와 같은 숫자들이 이친수이다. 그렇다면 이 숫자들을 나열하여 규칙성을 찾아보면 다음과 ..
[백준 2662] 기업투자
문제 링크 => 2662번: 기업투자 (acmicpc.net) 2662번: 기업투자 어떤 투자가가 여러 기업들에게 돈을 투자해서 최대의 이익을 얻고자 한다. 단, 투자는 만원 단위로 할 수 있으며 각 기업은 많이 투자할수록 많은 이익을 투자가에게 돌려준다. 돈을 투자하지 www.acmicpc.net 다이나믹 프로그래밍 문제이다. 투자액이 정해져 있고, 기업의 개수와 각 기업에 투자했을 경우에 얻게 되는 이익이 주어졌을 때 가장 많은 이익을 얻을 수 있는 투자방식과 이때의 이익금을 구해야 한다. 이때, 이차원 배열 arr, memo, invest, visited 에 대해서 설명하자면 다음과 같다. arr[x][y] => 기업 y에 금액 x 만원을 투자하는 경우 얻게 되는 이익 memo[x][y] => 기업..
[백준 2533] 사회망 서비스(SNS)
문제 링크 => 2533번: 사회망 서비스(SNS) (acmicpc.net) 2533번: 사회망 서비스(SNS) 첫 번째 줄에는 친구 관계 트리의 정점 개수 N이 주어진다. 단, 2 ≤ N ≤ 1,000,000이며, 각 정점은 1부터 N까지 일련번호로 표현된다. 두 번째 줄부터 N-1개의 줄에는 각 줄마다 친구 관계 트리의 에 www.acmicpc.net 다이나믹 프로그래밍 문제이다. 얼리 아답터인 경우와 얼리 아답터가 아닌 경우를 나누기 위해 2차원 배열 memo[1000001][2] 를 설정하였다. 얼리 아답터인 경우 (memo[x][1]) => memo[x][1] += min(dp(next, 1, x) + 1, dp(next, 0, x)) (그 다음 노드가 얼리 아답터인 경우와 얼리 아답터가 아닌 ..
[백준 2248] 이진수 찾기
문제 링크 => 2248번: 이진수 찾기 (acmicpc.net) 2248번: 이진수 찾기 N(1 ≤ N ≤ 31)자리의 이진수가 있다. 이러한 이진수 중에서, L(1 ≤ L ≤ N)개 이하의 비트만 1인 것을 크기 순으로 나열했을 때, I번째로 나오는 이진수를 구해내는 프로그램을 작성하시오. 이진수 www.acmicpc.net 다이나믹 프로그래밍 문제이다. N(1 ≤ N ≤ 31)자리의 이진수가 있다. 이러한 이진수 중에서, L(1 ≤ L ≤ N)개 이하의 비트만 1인 것을 크기 순으로 나열했을 때, I번째로 나오는 이진수를 구해내는 프로그램을 작성하시오. 이진수는 0으로 시작할 수도 있다. 2차원 배열 memo[x][y] 를 설정했을때 x는 자릿수를 결정하도록 하고 y는 해당 자릿수 x에서 비트 1를..
[백준 13398] 연속합 2
문제 링크 => 13398번: 연속합 2 (acmicpc.net) 13398번: 연속합 2 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 다이나믹 프로그래밍 문제이다. n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 수는 한개 이상 선택해야 하고, 수열에서 수를 하나 제거할 수 있다. (제거하지 않아도 된다) 이때 수를 제거하지 않고 얻어낼 수 있는 최댓값과 수열에서 수를 하나 제거하여 얻을 수 있는 최댓값 두가지로 분류하여 구해내야 한다. ..