1일1알

다이나믹 프로그래밍으로 해결할 수 있는 문제이다. 우리가 원하는 답은 1, 5, 12원의 동전으로 15원을 만들 때 가장 적게 드는 개수를 찾는것이다. 최종 답에서 top - down 방식으로 우선 생각해볼 때 두 가지 경우로 나눌 수 있다. 첫번째는 맨 뒤에 있는 12원의 동전을 포함한 경우이다. 이 경우는 같은 동전을 여러번 사용할 수 있으므로 1, 5, 12원으로 3원을 만드는 작은 문제로 나눌 수 있다. 이때는 12원의 동전을 하나 선택했기 때문에 +1을 해줘야한다. 두 번째는 12원의 동전을 포함하지 않은 경우이다. 이 경우는 1, 5원으로 15원을 만드는 작은 문제로 나눌 수 있다. 이 중 작은 값이 답이 되고, 나눠진 문제에서 같은 방식으로 또 나누면서 문제를 해결할 수 있다. 이 방식으로 ..

간단한 dp 문제이다. (r, c)에서의 사탕의 최대값은 (r - 1, c) , (r, c - 1), (r - 1, c - 1) 중 누적된 사탕의 개수가 가장 큰 값에 현재 위치의 사탕의 수를 더하면 된다. 여기서 만들 수 있는 점화식은 dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + v[i][j] 이다. #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; int main() { ios_base::sync_with_stdio(false); c..

단순한 dp문제처럼 보이지만 조금 생각해봐야 할 것이 있는 문제이다. 우선 3*2 타일은 이렇게 세 가지가 가능하고, 1*2와 2*1 타일만 사용하기 때문에 타일의 면적은 무조건 짝수가 나온다. 그러므로 3*홀수의 타일은 불가능하다는 것을 알 수 있다. 3*3 타일은 불가능하기 때문에, 3*4 타일의 경우를 생각해보면, 일단 3*2 타일의 경우에서 각각의 타일에 3*2타일을 또 붙이는 경우 일단 이렇게 9가지가 있고, 새로운 모양이 나온다. 이런 모양이 나오는데, 위아래로 뒤집어서 이런 모양이 2개가 나온다. 그래서 3*4 타일의 개수는 11개이다. 이제 3*6 타일을 살펴보면, 우선 이런 경우가 있다. 2칸 전의 타일에서 3가지 방법을 추가하는 경우 (dp[i-2]*3) 그리고 4칸 전부터 새로운 모양..

다이나믹 프로그래밍으로 해결할 수 있는 문제이다. top-down 방식으로 생각해 보면, 우선 예제에서 우리가 찾아야 할 최종 답은 1,2,5 동전을 이용해 10을 만들 수 있는 경우의 수를 찾는 것이다. 이것을 부분적인 문제로 나눠보면, 왼쪽은 5원을 한개 포함시킨 것이다. 5원을 포함시켰지만 또 포함시킬 수 있기 때문에 쓸 수 있는 동전은 같고, 10원에서 5원을 빼서 1,2,5를 사용해서 5원을 만들 수 있는 경우의 문제로 나눴다. 오른쪽은 5원을 포함시키지 않는 경우이다. 그렇기 때문에 1,2를 사용해서 10원을 만들 수 있는 경우의 문제로 나눴다. 여기서 알아낼 수 있는 점화식은 dp[i][j] = dp[i][j - v[i]] + dp[i-1][j] 이다. (v는 동전의 가치의 배열) 하지만 j..

다이나믹 프로그래밍으로 해결할 수 있는 문제이다. dp 테이블을 보면서 설명을 해보자면, 우선 행은 숫자의 길이이고 열은 맨 앞의 숫자이다. 문제에도 나와있듯이 숫자는 0으로 시작할 수 있다. 길이가 0개인 숫자는 없으니 0행은 모두 0이고, 길이가 1개인 숫자는 맨 앞 숫자가 무엇이든 1개이니 1행은 모두 1이다. 2행부터 살펴보자면, 우선 시작 숫자가 9이면 가능한 숫자는 99 하나밖에 없다. 그래서 9열은 우선 1로 채워준다. 그 다음부터는, 예를들어 7열을 보면 77,78,79가 가능한데, 이것을 1행과 연관지어서 생각해보면 1행의 7,8,9열은 길이가 1이고 시작하는 숫자가 7,8,9인 숫자들이기 때문에 당연히 7 뒤에 붙어셔 2자리 오르막 수로 만들 수 있다. 그래서 2행의 7열은 1행의 7,..

한정된 공간 안에 최대한의 가치를 넣는 배낭 채우기와 비슷한 문제이다. 카드의 개수가 무게, 가격을 가치라고 생각하면 된다. 하지만 한가지 다른 점이 있는데, 한 종류의 카드팩을 여러번 살 수 있다는 것이다. 점화식을 세우기 위한 과정을 우선 top-down 방식으로 생각해 보면 이런 식으로 그려볼 수 있다. 설명을 해보자면, 루트는 우리가 최종 구해야 할 답이고, N개의 카드를 최대한의 가격으로 구매할 때의 가격이다. 왼쪽으로 나눠진 부분은 4번 카드팩을 구매했을때의 상태이다. 4번 카드팩을 구매해서 카드의 개수가 4만큼 줄어들어서 0이 되었고, 카드팩은 구매했다고 사라지는게 아니기 때문에 사용가능한 카드팩은 그대로인 모습이다. 그리고 구매한 카드팩의 가격을 더해준 것이다. 오른쪽으로 나눠진 부분은 4..