[백준] 17130번: 토끼가 정보섬에 올라온 이유

https://www.acmicpc.net/problem/17130 17130번: 토끼가 정보섬에 올라온 이유 첫 줄에 격자의 크기 N과 M이 주어진다. 그 다음 줄부터 격자의 상태가 N개의 줄에 걸쳐 주어진다. '.'은 빈 공간을, '#'은 벽을, 'R'은 토끼를, 'C'는 당근을, 'O'는 정보섬 쪽문을 나타낸다. 'R'은 반 www.acmicpc.net 이동 경로의 조건에 따라 최댓값을 구하는 dp 문제다. 1. 문제 조건 1) 토끼는 오른쪽 위, 오른쪽, 오른쪽 아래로만 이동이 가능하다. 2) 이동하면서 최대한 많은 당근을 지나서 탈출까지 해야 한다. 3) 벽은 지나갈 수 없다. 4) 문을 통해 나갈 수 있는데, 문에 도착해도 나가지 않을 수 있다. 5) 처음에 토끼는 지도 상의 어느 곳에나 위치..

[백준] 13707번: 합분해 2

https://www.acmicpc.net/problem/13707 13707번: 합분해 2 첫째 줄에 두 정수 N(1 ≤ N ≤ 5,000), K(1 ≤ K ≤ 5,000)가 주어진다. www.acmicpc.net 숫자의 조합을 만들어서 생각해야 하는 dp 문제다. 1. 문제 조건 1) 0 ~ N 까지의 수 K개를 더해서 N을 만드는 경우의 수를 구해야 한다. 2) 순서가 바뀐 경우는 다른 경우로 센다. 3) 같은 수를 중복해서 사용할 수 있다. 2. dp 배열 정의 문게가 간단한 만큼 주어진 미지수에 따라 dp 배열을 정의하면 된다. #define MAXK 5001 #define MAXN 5001 #define DIVIDER 1'000'000'000 // dp[k][n] = 0 ~ n 까지의 수 k개..

[백준] 2600번: 구슬게임

https://www.acmicpc.net/problem/2600 2600번: 구슬게임 첫 줄에는 한번에 꺼낼 수 있는 구슬의 개수를 나타내는 세 개의 정수 b1, b2, b3 가 나타난다. 그 다음 5개의 각 줄에는 두 통속에 처음 담겨있는 구슬의 개수 k1, k2가 각각 표시되어 있다. www.acmicpc.net 재귀를 이용해서 현재 상태의 승패 유무를 기록하는 dp 문제다. 1. 문제 조건 1) 2명의 플레이어가 번갈아가며 게임을 한다. 항상 최적으로만 행동한다. 2) 2개의 상자가 있는데, 한 번에 한 상자에서만 구슬을 꺼낼 수 있다. 3) 한 번에 꺼낼 수 있는 구슬의 개수는 정해져 있다. 4) 꺼낼 수 있는 구슬의 개수는 3가지가 주어진다. 5) 어떻게 해도 구슬을 꺼낼 수 없는 사람이 진다..

[백준] 14722번: 우유 도시

https://www.acmicpc.net/problem/14722 14722번: 우유 도시 영학이는 딸기우유, 초코우유, 바나나우유를 좋아한다. 입맛이 매우 까다로운 영학이는 자신만의 우유를 마시는 규칙이 있다. 맨 처음에는 딸기우유를 한 팩 마신다. 딸기우유를 한 팩 마신 후 www.acmicpc.net 이전의 상태를 유지하면서 최댓값을 구하는 dp 문제다. 개인적으로 어려웠던 문제다. 문제 구현 자체는 할만 했는데, 초기 조건을 하나 놓치는 바람에 오래 걸린 문제다. (N X N) 크기의 map에 3종류의 우유가 있는데, 반드시 0 → 1 → 2 → 0 ... 의 순서로 우유를 마셔야 한다. 어떤 좌표에 도착했을 때, 그 우유를 마실 수도, 안 마실 수도 있다. 따라서 좌표마다 이전에 마지막으로 마..

[백준] 5569번: 출근 경로

https://www.acmicpc.net/problem/5569 5569번: 출근 경로 상근이가 사는 도시는 남북 방향으로 도로가 w개, 동서 방향으로 도로가 h개 있다. 남북 방향 도로는 서쪽부터 순서대로 번호가 1, 2, ..., w로 매겨져 있다. 또, 동서 방향 도로는 남쪽부터 순서대 www.acmicpc.net 조건이 붙은 경로 개수를 구하는 dp 문제다. 최단 경로로 이동하되 방향을 연속으로 틀지 못하는 조건이 걸려있다. 항상 오른쪽 또는 위쪽으로만 이동이 가능하다. 따라서 방향을 연속으로 틀었는지를 기록해두어야 하는데, 이전 교차로로 온 방향과 지금 교차로로 온 방향에 따라 dp 값을 갱신하면 된다. dp 배열을 아래와 같이 정의한다. #define MAXH 101// 세로 최대 길이 #d..

[백준] 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 배열을 아래와 같이 정의한다...