[백준] 2157번: 여행

https://www.acmicpc.net/problem/2157 2157번: 여행 첫째 줄에 N(1 ≤ N ≤ 300), M(2 ≤ M ≤ N), K(1 ≤ K ≤ 100,000)가 주어진다. K는 개설된 항공로의 개수이다. 다음 K개의 줄에는 각 항공로에 대한 정보를 나타내는 세 정수 a, b, c(1 ≤ a, b ≤ N, 1 ≤ c ≤ 1 www.acmicpc.net 그래프 스타일의 dp 문제다. a 도시에서 b 도시로 이동하는 경로가 0개 이상 있고 각 경로마다 점수가 있을 때 M개 이하의 도시를 거쳐 1번 도시에서 N번 도시로 이동했을 때의 최댓값을 구하는 문제다. dp 배열을 아래와 같이 정의한다. #define MAXN 301 #define MAXM 301 // dp[n][m] = n번 도시..

[백준] 4781번: 사탕 가게

https://www.acmicpc.net/problem/4781 4781번: 사탕 가게 각 테스트 케이스의 첫째 줄에는 가게에 있는 사탕 종류의 수 n과 상근이가 가지고 있는 돈의 양 m이 주어진다. (1 ≤ n ≤ 5,000, 0.01 ≤ m ≤ 100.00) m은 항상 소수점 둘째자리까지 주어진다. 다음 n개 www.acmicpc.net 배낭 문제로 해결하는 dp 문제다. 사탕 구매가 가능한 돈의 양이 소수로 주어진다는 점 빼고는 이전까지 풀어봤던 배낭문제와 크게 다를 바가 없어 보였다. dp 배열을 아래와 같이 정의한다. #define MAXM 10001 // dp[m] = (m / 100.0)원을 사용했을 때 얻을 수 있는 최대 칼로리 int dp[MAXM]; 사용할 수 있는 돈을 기준으로 최대..

[백준] 2634번: 색종이 올려 놓기

https://www.acmicpc.net/problem/2643 2643번: 색종이 올려 놓기 첫 번째 줄에는 색종이의 장수가 주어진다. 다음 줄부터 각 줄에 색종이의 두 변의 길이가 주어진다. 두 변의 길이는 한 칸 띄어 주어진다. 색종이의 최대 장수는 100이고, 각 변의 길이는 1000보다 www.acmicpc.net LIS를 활용한 dp 문제다. 문제가 다소 복잡해보이지만 지금까지 많이 풀었던 가장 긴 증가하는 부분 수열(LIS) 을 응용하면 풀 수 있다. 여느 LIS 문제처럼 dp 배열을 아래와 같이 정의한다. #define MAXN 101 // dp[n] = [1, n] 구간에서 쌓을 수 있는 색종이의 최대 수 int dp[MAXN]; 사실 엄밀히 말하면 내가 풀려는 방식은 LDS (Long..

[백준] 1695번: 팰린드롬 만들기

https://www.acmicpc.net/problem/1695 1695번: 팰린드롬 만들기 앞에서 뒤로 보나, 뒤에서 앞으로 보나 같은 수열을 팰린드롬 이라고 한다. 예를 들어 {1}, {1, 2, 1}, {1, 2, 2, 1}과 같은 수열은 팰린드롬 이지만, {1, 2, 3}, {1, 2, 3, 2} 등은 팰린드롬이 아니다. 한 수열 www.acmicpc.net 팰린드롬을 이용한 dp 문제다. 팰린드롬 문제는 보고자 하는 구간 [s, e] 에서 s와 e에 해당하는 값이 같은지를 확인해서 dp 배열을 구성해야 한다. dp 배열을 아래와 같이 정의한다. #define MAXN 5001 #define INF 987654321 // dp[s][e] = [s, e] 구간에서 팰린드롬을 만들기 위해 넣어햐 하..

[백준] 2698번: 인접한 비트의 개수

https://www.acmicpc.net/problem/2698 2698번: 인접한 비트의 개수 첫째 줄에 테스트 케이스의 수 T(1 ≤ T ≤ 1,000)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 수 2개가 공백으로 구분되어 이루어져 있다. 첫 번째 수는 n이고, 두 번째 수는 k이다. n과 www.acmicpc.net 길이 N과 인접한 비트의 개수 K가 주어졌을 때 가능한 모든 경우의 수를 계산하는 dp 문제다. 처음에 문제가 직관적으로 이해가 안 갔다. 그냥 어떤 1이 있을 때, 그 주변에 연속된 나머지 1의 개수를 구하라는 의미다. 문제를 이해하고 나니, 길이 n과 인접한 비트의 개수 k, 그리고 마지막 숫자를 기록해두어야겠다는 생각이 들었다. dp 배열을 아래와 같이 정의한다...

[백준] 1563번: 개근상

https://www.acmicpc.net/problem/1563 1563번: 개근상 백준중학교에서는 학기가 끝날 무렵에 출결사항을 보고 개근상을 줄 것인지 말 것인지 결정한다. 이 학교는 이상해서 학생들이 학교를 너무 자주 빠지기 때문에, 개근상을 주는 조건이 조금 독 www.acmicpc.net 이전의 상태를 고려해야 하는 dp 문제다. 지각을 누적 2번 하거나 결석을 연속 3번 하면 개근상을 받지 못 한다. 따라서 지각의 누적 횟수와 연속 결석 횟수를 저장하는 dp 배열을 만들어야 한다. dp 배열을 아래와 같이 정의한다. #define MAXN 1001// 전체 날짜 수 #define MAXL 2// 지각 가능 날짜 수 #define MAXA 3// 연속 결석 가능 날짜 수 #define DIVI..

[백준] 14852번: 타일 채우기 3

https://www.acmicpc.net/problem/14852 14852번: 타일 채우기 3 첫째 줄에 경우의 수를 1,000,000,007로 나눈 나머지를 출력한다. www.acmicpc.net 이전의 모양을 고려해서 해결하는 dp 문제다. 여느 타일 채우기 문제가 그렇듯... 특수한 경우를 생각해주면 되겠다. 우선 dp 배열을 아래와 같이 정의한다. #define MAXN 1000001 #define DIVIDER 1000000007 typedef long long ll; // dp[n] = (2 X n)을 채우는 경우의 수 ll dp[MAXN]; // sum[n] = dp[0] ~ dp[n] 까지의 누적합 ll sum[MAXN]; 정답 자체의 값은 int 범위를 넘지 않지만 연산 중의 값디 i..

[백준] 13302번: 리조트

https://www.acmicpc.net/problem/13302 13302번: 리조트 수영이는 여름방학을 맞이하여 많은 놀이 시설이 있는 KOI 리조트에 놀러가려고 한다. 리조트의 하루 이용권의 가격은 만원이다. 하지만 리조트의 규모는 상상을 초월하여 모든 시설을 충분히 www.acmicpc.net 리조트를 방문할 수 있는 모든 날을 최소 비용으로 방문하는 dp 문제다. 1일권, 3일권, 5일권 티켓이 있고 3일권과 5일권을 구입하면 쿠폰을 각각 1개, 2개를 준다. 쿠폰 3개는 1일권 1장으로 사용할 수 있다. N일 중 방문할 수 있는 모든 날에 리조트를 방문한다고 할 때의 최소 비용을 구하는 문제다. 다른 분들은 보통 재귀로 풀었던데, 나는 dp 로 풀어보기로 했다. dp 배열을 아래와 같이 정의..

[백준] 10422번: 괄호

https://www.acmicpc.net/problem/10422 10422번: 괄호 ‘(‘, ‘)’ 문자로만 이루어진 문자열을 괄호 문자열이라 한다. 올바른 괄호 문자열이란 다음과 같이 정의된다. ()는 올바른 괄호 문자열이다. S가 올바른 괄호 문자열이라면, (S)도 올바른 괄호 www.acmicpc.net 올바른 괄호 문자열을 만드는 경우의 수를 찾는 dp 문제다. dp 배열을 아래와 같이 정의한다. #define MAXN 5001 #define INF 1000000007 typedef long long ll; // dp[n] = 길이가 n 인 올바른 괄호 문자열의 개수 ll dp[MAXN]; 실제 출력되는 dp 의 값은 int 범위 안에 있으나, 연산 과정에서 int 범위를 넘어가는 경우가 발생..

[백준] 2602번: 돌다리 건너기

https://www.acmicpc.net/problem/2602 2602번: 돌다리 건너기 첫째 줄에는 마법의 두루마리에 적힌 문자열(R, I, N, G, S 로만 구성된)이 주어진다. 이 문자열의 길이는 최소 1, 최대 20 이다. 그 다음 줄에는 각각 와 를 나타내는 www.acmicpc.net 이전에 밟은 글자와 다리를 고려해야 하는 dp 문제다. 이제 이런 문제를 볼 때마다, 다차원으로 dp 배열을 만들어야겠다는 생각부터 든다. 다리는 총 2개이며 번갈아 밟아야 한다. 글자는 최대 20글자이며, 반드시 순서대로 모두 밟아야 한다. 따라서 dp 배열을 아래와 같이 정의한다. #define MAXT 21// 밟아야 하는 문자열의 최대 길이 #define MAXL 101// 다리의 최대 길이 char..