문제https://www.acmicpc.net/problem/2533 문제 이해SNS 네트워크는 트리(사이클 없음) 로 주어진다.어떤 사람이 정보를 전달받으려면 그 사람의 이웃 중 적어도 한 명은 ‘얼리어답터’ 여야 한다.모든 사람이 정보를 전달받도록 할 때, 필요한 얼리어답터의 최소 수를 구한다.TIP: “모든 간선마다 양 끝점 중 최소 한 쪽은 선택되어야 함” 이라고 생각하면 이해하기 쉽다. 풀이 아이디어: 트리 DP루트를 1로 잡고 DFS로 트리를 내려가며 탐색한다. 상태 정의dp[0][node] : node가 얼리어답터가 아닐 때, node의 서브트리에서 필요한 최소 얼리어답터 수dp[1][node] : node가 얼리어답터일 때, node의 서브트리에서 필요한 최소 얼리어답터 수 점화식현재 정점..

문제https://www.acmicpc.net/problem/15486 문제 이해N일 동안 가능한 상담 일정이 주어진다.상담의 기간, 수익N + 1일째 되는 날 퇴사하기 위해, 퇴사 전(N일 내)에 끝나는 상담들을 선택해 최대 수익을 구한다.하루에 하나의 상담만 할 수 있어서, 상담을 시작하면 해당 상담 기간 동안 다른 상담은 할 수 없다.끝나는 날이 N일을 넘어가면 그 상담은 수행할 수 없다. DP 구현dp[i]: i일까지의 최대 이익전날 이익 저장 dp[i] = max(dp[i], dp[i-1])i일에 상담을 시작끝나는 날: end = i + consults[i].t - 1퇴사 전에 끝나는 상담만 유효: end i - 1일까지의 최대 수익에 이번 상담의 수익을 더해서 최댓값 반영dp[end] = ma..

문제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..