문제https://www.acmicpc.net/problem/9084문제 이해N가지 동전으로 금액 M을 만드는 모든 방법의 수를 구한다.문제 풀이🔍 접근이 문제는 대표적인 Unbounded Knapsack 문제다.아래의 배낭 문제에서 각 물건을 1번만 선택할 수 있었던 점과 다르게, 같은 동전을 여러번 넣을 수 있다. [BOJ][C++] 백준 12865번: 평범한 배낭문제https://www.acmicpc.net/problem/12865 문제 이해최대 무게(K)가 정해진 배낭에 물건을 넣는다. N개의 물건에는 각각 무게(W)와 가치(V)가 있다.배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 구한다.y-e-99.tistory.com 💡 Dynamic Programming목표 금액을 인덱스로, 목표 금..

문제https://www.acmicpc.net/problem/12865 문제 이해최대 무게(K)가 정해진 배낭에 물건을 넣는다. N개의 물건에는 각각 무게(W)와 가치(V)가 있다.배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 구한다. 문제 풀이❔ 브루트포스물건의 가능한 모든 조합을 구한다.N개의 물건에 대해 넣을지 말지를 모두 시도한다. O(2^N)이고, N ≤ 100이므로 제한시간 초과 ❔ 백트래킹물건의 가능한 모든 조합을 구하면서 최대 무게를 넘어가는 경우를 가지치기로 줄인다.최악의 경우로, 모든 조합이 최대 무게를 넘어가지 않으면, 브루트포스와 같아진다. 💡 Dynamic ProgrammingDP를 통해 이전 결과를 저장해서 중복 계산을 피한다.'배낭의 최대 무게'를 인덱스로, 가치합의 최댓값..

문제https://www.acmicpc.net/problem/1890 문제 이해수가 적혀 있는 N×N 게임판에서 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 따라 점프한다.규칙에 맞게 이동할 수 있는 경로의 개수를 구한다. 규칙각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거리를 의미한다.0은 종착점을 의미한다.현재 칸에 적혀있는 수만큼 오른쪽이나 아래로만 이동 가능하다.한 번 점프할 때 방향을 바꿀 수 없다. 오른쪽으로 또는 아래로 점프를 하는 두 경우만 존재한다. 문제 풀이 🔍 접근 각 칸마다 현재 칸까지의 경로의 개수를 저장한다. 💡 Dynamic Programming칸에 적힌 수만큼 이동해서 해당 칸까지의 경로의 개수를 저장한다.첫 번째 칸(경로의 개수 1)부터 시작한다.오른쪽으로 ..

문제https://www.acmicpc.net/problem/2579 문제 이해점수가 쓰여 있는 계단을 밟는 게임에서 얻을 수 있는 총 점수의 최댓값을 구한다. 계단 오르는 규칙한 번에 한 계단 또는 두 계단씩 오를 수 있다.연속된 세 계단을 밟으면 안 된다.마지막 도착 계단은 반드시 밟아야 한다.시작점은 계단에 포함되지 않는다. 문제 풀이 🔍 접근 각 계단마다 현재 계단까지의 점수 최댓값을 구해서 저장한다. 💡 Dynamic Programming각 계단은 1칸 또는 2칸 전 계단에서 온 것이므로 max(1칸 전 최댓값, 2칸 전 최댓값) + 현재 계단 점수로 식을 세울 수 있다.하지만 연속 세 칸을 밟으면 안 되는 조건을 만족하지 못한다.이 조건을 고려해서 경우의 수를 생각해보면 아래와 같이 나타낼..

문제https://www.acmicpc.net/problem/9184풀이문제에 나와있는 함수를 작성하면 아래와 같다.int w(int a, int b, int c) { if (a 20 || b > 20 || c > 20) return w(20, 20, 20); else if (a 재귀의 횟수를 줄이기 위해 w의 결과 값을 dp 배열에 저장할 수 있다.a, b, c의 값에 따른 결과값을 저장하기 위한 3차원 dp 배열을 선언한다.w(a, b, c) 함수를 실행했을 때 배열에 이미 저장된 값이면, 재귀 과정을 생략하고 그 값을 불러온다.배열에 값을 저장할 때 인덱스에 음수 또는 20 이상의 수가 들어가지 않도록 유의한다.코드#include #include using namespac..