문제 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 설명 n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 사용해서, 가치의 합이 k원이 되도록 하고 싶다. 각각의 동전은 몇 개라도 사용할 수 있다. 그 경우의 수를 쓰시오. ! 사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다. 풀이 방식 이 문제는 DP 알고리즘을 통해 푸는 문제이다.즉, 전의 결과의 값이 현재의 값을 정하는데 반영이 된다. 다음 예시를 통해 알아보자. 3 10 1 2 5 만약 n = 3, k=..

문제 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 문제 설명 오르막 수는 수가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. - 가능: 2234, 3678, 11119 - 불가능: 2232, 3676, 91111 수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하라. 0으로 시작가능. 풀이 방식 다음 이미지대로 하면 된다. 이게 DP의 방식 인지는 모르겠는데.. 이전의 값을 가지고 와서 현재의 값을 만들어 낸다. 다음..

다이나믹 프로그래밍(동적 계획법) 이란? 다이나믹 프로그래밍은 재귀에 대한 최적화이다. 이말은 중복된 부분에 대한 문제가 있다면, 이에 대한 결과를 저장해둔다. 그리고 동일한 부분에서의 문제가 다시 발생한다면, 이 결과를 재사용하는 방법이다. 이런 사례는 피보나치 수열에서 쉽게 찾아볼 수 있다. 피보나치 수열의 점화식은 다음과 같다. f(n) = f(n - 1) + f(n - 2) 이때 n = 4라고 한다면, f(4) = f(3) + f(2) 를 구해야 하는데, 이때 전에 구해두었던 f(3) 과 f(2)의 값을 다시 구하지 않고 저장해두었다가 다시 사용하는 것을 의미한다. 특징 커다란 문제를 나누어 해결하는 편이다. 앞서 말했듯이, 이전에 풀었던 문제와 동일한 문제일 경우, 다시 연산 하는 것이 아니라 ..

문제 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 문제 설명 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 위 그림은 크기가 5인 정수 삼각형의 한 모습이다. 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구해야 한다. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다. 풀이 방식 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 다음 n = 5일때 다음과 같은 삼각형이 있다고 하자. 다음 풀이의 핵심은 이전 값의 계산을 ..

문제 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 문제 설명 수열 A가 주어졌을 때, 가장 긴 오름차순의 수열을 구하는 프로그램을 작성해야 한다. 풀이 방식 A = { 70, 30, 50, 60, 70, 0, 10} 다음과 같은 수열이 있다고 하자. brute force식으로 구해보면 다음과 같다. 어떻게 해도 이 블로그 보다 설명을 잘 할 수 없으니 모르겠다면 참고 하도록 하자. 백준 11053번 가장 긴 증가하는 부분 수열 파..