[백준] 1577번: 도로의 개수

https://www.acmicpc.net/problem/1577 1577번: 도로의 개수 첫째 줄에 도로의 가로 크기 N과 세로 크기 M이 주어진다. N과 M은 100보다 작거나 같은 자연수이고, 둘째 줄에는 공사중인 도로의 개수 K가 주어진다. K는 0보다 크거나 같고, 50보다 작거나 같은 자 www.acmicpc.net 끊어진 도로를 어떻게 표현하는지가 관건인 dp 문제다. 문제에서 최단 거리로만 이동한다고 하였으므로 좌상단에서 우하단으로 이동하기 위해 오른쪽 또는 아래쪽으로만 이동이 가능하다. 따라서 dp 배열은 위의 경우와 왼쪽 경우를 더한 값을 저장해두면 된다. 계산을 편리하게 하기 위해, 맨 위와 맨 왼쪽을 0으로 padding 하여 구현한다. dp 배열을 아래와 같이 정의한다. #defi..

[백준] 3067번: Coins

https://www.acmicpc.net/problem/3067 3067번: Coins 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 모든 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어 30원을 만들기 위해 www.acmicpc.net dp 중 전형적인 배낭 문제다. dp 배열을 아래와 같이 정의한다. #define MAXM 10001 #define MAXN 21 // dp[m] = m원을 만들 수 있는 모든 경우의 수 int dp[MAXM]; int coin[MAXN; coin 배열에는 사용할 수 있는 동전의 액수가 들어간다. 점화식을 구하기 위해 base 조건과 귀납적 정의를 알아본다. 1) n = 0 ..

[백준] 2591번: 숫자카드

https://www.acmicpc.net/problem/2591 2591번: 숫자카드 1부터 34까지 수가 적힌 카드가 충분히 많이 있다. 이들 중 몇 장을 일렬로 늘어놓고, 그 숫자를 차례로 적었다. 예를 들어 아래와 같이 카드가 놓인 경우 숫자를 차례로 적으면 27123이 된다. 나중 www.acmicpc.net 숫자의 범위를 생각해서 해결하는 dp 문제다. dp 배열을 아래와 같이 정의한다. #define MAXN 42 // dp[n] = str[0] ~ str[n-1] 까지의 모든 경우의 수 // dp 배열은 1부터 시작하는 것으로 구현 int dp[MAXN]; char str[MAXN]; 우리가 생각해야할 조건은 크게 2가지다. 1) n번째 숫자를 1자리 수로 생각하는 경우 2) n-1번째, ..

[백준] 2410번: 2의 멱수의 합

https://www.acmicpc.net/problem/2410 2410번: 2의 멱수의 합 첫째 줄에 경우의 수를 출력한다. 답이 커질 수 있으므로 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 점화식을 구상해서 해결하는 dp 문제다. dp 배열을 아래와 같이 정의한다. #define MAXN 1000001 #define DIVIDER 1000000000 // dp[n] = n을 2의 멱수로 나타낼 수 있는 경우의 수 int dp[MAXN]; 점화식을 세우기 위해 오름차순으로 몇 가지 케이스를 생각해 본다. 1) 1 = 1 (base) 2) 2 = 1+1 / 2 3) 3 = 1+1+1 / 1+2 4) 4 = 1+1+1+1 / 1+1+2 // 2+2 / 4 5) 5 ..

[백준] 2229번: 조 짜기

https://www.acmicpc.net/problem/2229 2229번: 조 짜기 알고스팟 캠프에 N(1 ≤ N ≤ 1,000)명의 학생들이 참여하였다. 학생들은 열심히 공부를 하고 있었는데, 어느 날 조별 수업을 진행하기로 하였다. 조별 수업의 목적은 잘 하는 학생들과 덜 잘 하는 www.acmicpc.net 최대 최소를 이용한 DP 문제다. dp 배열을 아래와 같이 정의한다. #define MAXN 1001 // dp[n]: 1 ~ n번째 학생까지 조를 나눴을 때의 가장 높은 값 int dp[MAXN]; n번째 학생을 추가했을 때의 가장 높은 값은 아래 경우 중의 최댓값으로 구할 수 있다. 1) dp[n-1] + (n) 번째 학생 1명인 조의 값 2) dp[n-2] + (n-1, n) 번째 학생..

[백준] 2666번: 벽장문의 이동

https://www.acmicpc.net/problem/2666 2666번: 벽장문의 이동 첫 번째 줄에 벽장의 개수를 나타내는 3보다 크고 20보다 작거나 같은 하나의 정수, 두 번째 줄에 초기에 열려있는 두 개의 벽장을 나타내는 두 개의 정수, 그리고 세 번째 줄에는 사용할 벽장들 www.acmicpc.net 완전탐색과 재귀를 이용한 dp 문제다. dp 배열을 아래와 같이 정의한다. #define MAXN 22 // dp[i][j][k] = i번째 문을 열어야 할 때, 현재 j와 k번째 문이 열려있다. int dp[MAXN][MAXN]MAXN]; 이번에 열어야 하는 문과 가까운 문을 연다고 해서 반드시 최적이 보장되지는 않는다. 즉, greedy하지 않다. 따라서 왼쪽과 오른쪽을 모두 변화시키면서,..

[백준] 1106번: 호텔

https://www.acmicpc.net/problem/1106 1106번: 호텔 첫째 줄에 C와 형택이가 홍보할 수 있는 도시의 개수 N이 주어진다. C는 1,000보다 작거나 같은 자연수이고, N은 20보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 각 도시에서 홍보할 때 www.acmicpc.net DP 중에 전형적인 배낭 문제다. DP 배열을 아래처럼 정의한다. #define MAXC 100001// 1000명 X 100원 = 100000원 int dp[MAXC];// dp[i]: i원을 사용했을 때, 늘어난 최대 사람 수 사용한 금액을 기준으로 dp 배열을 만든다. 최대 사용 가능 금액은, 최악의 경우 최대 1,000명에 1인당 최대 100원이 든다고 생각했을 때 100,000원 이라..