문제 링크https://www.acmicpc.net/problem/17845 문제 요약최대 공부시간 \(N\)과 과목 수 \(K\)가 주어진다. 이어서 각 과목 \(i\)의 중요도 \(I_i\)와 필요한 공부시간 \(T_i\)가 주어진다. 최대 공부시간 \(N\)을 초과하지 않으면서 중요도 합이 최대가 되도록 과목을 선택할 때, 최대 중요도를 구하는 문제이다. 문제 풀이이 문제는 전형적인 배낭 문제(Knapsack Problem)로 동적 계획법(Dynamic Programming)을 이용해 풀 수 있다. 동적 계획법은 Top Down 방식과 Bottom Up 방식으로 풀 수 있는데, 여기서 두 가지 방법 모두를 이용해 문제를 푸는 방법을 소개한다. Top Down 방식으로 문제 풀기동적 계획법을 Top ..
1. 방 배정 https://www.acmicpc.net/problem/13300 학생들을 학년별, 성별로 한 방에 배정하려고 하는데 필요한 최소 방의 개수를 구하는 문제다. 문제에서 요구하는 대로 학년별, 성별로 인원을 센 다음에 각각에 대해 최소로 필요한 방의 개수를 센 뒤 더해주면 된다. 이는 나눗셈과 나머지 연산으로 쉽게 구할 수 있다. #include int n, k, s, y, C[7][2]; int main() { scanf("%d%d", &n, &k); while (n--) { scanf("%d%d", &s, &y); ++C[y][s]; } int ans = 0; for (int i = 1 ; i
문제 링크 https://www.acmicpc.net/problem/5626 문제 요약 현재 제단의 상태가 주어진다. 도둑이 훔쳐간 부분은 -1이고 남아있는 부분은 정수로 표현이 되어있다. 이 때 가능한 초기 제단의 경우의 수를 구하는 문제다. 문제에서 초기 제단을 만드는 방법은 주어진다. 문제 풀이 모든 열의 초기값은 0이다. 이 때 한가지 연산을 할 수 있다. 같은 높이를 가지는 연속하는 열들을 선택한다. 그리고 선택한 연속된 열 중 처음 열과 가장 끝 열을 제외한 모든 열의 높이를 1씩 높인다. 이 연산을 사용해서 제단을 만들어 나갈 수 있다. 이 연산을 잘 생각해 본다면 두가지 통찰을 얻을 수 있다. 1. 첫 번째 제단과 마지막 열의 높이는 0이다. 2. 인접한 두 열의 높이차는 최대 1이다. 이..
문제 링크 https://www.acmicpc.net/problem/1814 문제 요약 크기가 \(N\)인 트리가 주어진다. 이 트리의 정점들을 \(M\)가지의 색으로 칠하려고 하는데 각각의 색들은 색을할 할 때 비용이 든다. 또한 인접한 정점은 서로 색이 달라야 한다. 제약조건을 지키면서 모든 정점들을 칠할 때 드는 최소 비용을 구하는 문제다. 문제 풀이 주어지는 입력이 트리이기 때문에 \(dp\)로 쉽게 풀릴것 같은 생각이 든다. 아래와 \(dp\ table\)을 생각해보자. \(dp[here][color]=\ \)\(here\)를 \(color\)로 색칠하고 \(here\)의 \(subtree\)를 색칠하는데 드는 최소 비용 이 식은 어떻게 채워질 수 있을까? 이식은 아래와 같을 것이다. \(dp[..
