[백준] 14846번: 직사각형과 쿼리

https://www.acmicpc.net/problem/14846 14846번: 직사각형과 쿼리 첫째 줄에 N (1 ≤ N ≤ 300)이 주어진다. 다음 N개의 줄에는 행렬의 정보가 주어지며, 각 줄은 N개의 수로 이루어져 있다. 행은 위에서부터 아래로, 열은 왼쪽부터 오른쪽으로 번호가 매겨져 있으며 www.acmicpc.net 누적합을 이용한 dp 문제다. 1. 문제 조건 1) 왼쪽 위가 (x1, y1), 오른쪽 아래가 (x2, y2) 로 이루어진 직사각형이 쿼리로 주어진다. 2) 쿼리마다 주어진 직사각형에 포함된 서로 다른 정수의 개수를 출력한다. 3) 정수는 1 ~ 10 까지의 자연수다. 4) 전체 행렬의 크기는 (N × N) 이고, 시작 좌표는 (1, 1) 이다. 2. dp 배열 정의 행렬에 들..

[백준] 2073번: 수도배관공사

https://www.acmicpc.net/problem/2073 2073번: 수도배관공사 아기염소들이 언덕에서 풀을 뜯고 놀다 보면 항상 도중에 목이 마르곤 했다. 그들은 불편함을 참지 못하고 수도관을 설치하여 거리 D(7 ≤ D ≤ 100,000)만큼 떨어진 곳의 강에서 물을 끌어오기로 www.acmicpc.net 조건이 추가로 붙은 배낭 문제다. 1. 문제 조건 1) 전체 길이가 D가 되도록 수도관을 연결할 때의 최대 용량을 출력한다. 2) 전체 파이프의 용량은, 연결하는데 사용된 파이프의 용량 중 최솟값이다. 3) 한 파이프는 다른 곳에 재사용할 수 없다. (당연하다.) 2. dp 배열 정의 최소? 최대? 가 난잡하게 다가와서 헷갈리지만 일반 배낭 문제와 크게 다를 바가 없다. 현재 길이 N 까지..

[백준] 5546번: 파스타

https://www.acmicpc.net/problem/5546 5546번: 파스타 상근이는 매일 저녁으로 파스타를 만들어 먹는다. 상근이가 만들 수 있는 파스타는 총 세 종류로 토마토 소스, 크림 소스, 바질 소스이다. 상근이는 앞으로 N일 동안 먹을 파스타를 계획하려고 www.acmicpc.net 이전 기록을 토대로 현재 경우의 수를 갱신하는 dp 문제다. 1. 문제 조건 1) 1 ~ N 일 동안 파스타를 먹을 수 있는 방법의 가짓수를 출력한다. 2) 파스타는 토마토, 크림, 바질이 있다. 3) 3일 연속 같은 파스타를 먹을 수 없다. 4) N일 중 K일에는 그 날 먹을 파스타가 정해져 있다. 2. dp 배열 정의 3일 연속 같은 파스타를 먹지 못하니까, 처음에는 전 날과 전전 날에 먹은 파스타를 ..

[백준] 2411번: 아이템 먹기

https://www.acmicpc.net/problem/2411 2411번: 아이템 먹기 첫째 줄에 N, M(1 ≤ N, M ≤ 100), A(1 ≤ A), B(0 ≤ B)가 주어진다. A는 아이템의 개수이고, B는 장애물의 개수이다. 다음 A개의 줄에는 아이템의 위치, B개의 줄에는 장애물의 위치가 주어진다. 위치를 www.acmicpc.net 특정한 위치를 지날 때의 경로 개수를 구하는 dp 문제다. 1. 문제 조건 1) (1, 1) → (N, M) 까지 도달하는 경로의 수를 출력해야 한다. 2) 위쪽과 오른쪽으로만 이동할 수 있다. 3) 이동 중에 모든 아이템을 먹어야 한다. 4) 장애물은 지날 수 없다. 2. dp 배열 정의 전형적인 경로 탐색 문제다. 다만 모든 아이템을 먹어야 한다는 점에서,..

[백준] 17208번: 카우버거 알바생

https://www.acmicpc.net/problem/17208 17208번: 카우버거 알바생 중간고사 종료를 기념해 계획 없이 돈을 쓰던 영석이는 안타깝게도 통장 잔고가 100원도 남지 않게 되었고, 결국 영석이는 카우버거 주방 알바를 하기로 했다. 카우버거는 치즈버거와 감자튀 www.acmicpc.net 2차원 배낭 문제로 해결하는 dp 문제다. 1. 문제 조건 1) 주어진 치즈버거와 감자튀김을 가지고 처리할 수 있는 최대 주문 수를 출력한다. 2) 한 주문에 적힌 치즈버거와 감자튀김은 반드시 모두 처리해야 한다. 3) 주문이 들어온 순서는 중요하지 않다. 4) 한 주문은 중복해서 처리할 수 없다. 2. dp 배열 정의 지금까지 풀었던 배낭 문제의 2차원 버전이다. 어려울 것 없이, 치즈버거와 감..

[백준] 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..