[백준] 17090번: 미로 탈출하기

https://www.acmicpc.net/problem/17090 17090번: 미로 탈출하기 크기가 N×M인 미로가 있고, 미로는 크기가 1×1인 칸으로 나누어져 있다. 미로의 각 칸에는 문자가 하나 적혀있는데, 적혀있는 문자에 따라서 다른 칸으로 이동할 수 있다. 어떤 칸(r, c)에 적힌 문 www.acmicpc.net 이미 지나간 경로를 재사용하는 dp 문제다. 1. 문제 조건 1) N × M 크기의 미로가 있고, 각 칸에는 이동 방향을 나타내는 문자가 적혀있다. 2) 반드시 그 칸에 적힌 방향으로 이동해야 한다. 3) 미로 경계 밖으로 나가는 경우를 탈출이라고 한다. 4) 탈출이 가능한 시작점의 개수를 출력한다. 2. dp 배열 정의 이동할 때에는 반드시 그 칸에 적힌 방향으로만 가능하다. 그..

[백준] 1937번: 욕심쟁이 판다

https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net 최대 이동 경로의 길이를 구하는 dp 문제다. 1. 문제 조건 1) N × N 크기의 2차원 배열이 주어진다. 2) 판다가 이동할 수 있는 최대 이동 경로의 길이를 출력한다. 3) 판다는 상하좌우로 이동할 수 있다. 4) 판다는 현재 칸보다 대나무가 더 많은 곳으로 이동한다. 2. dp 배열 정의 일반 dfs 문제로 생각해서 모든 경로를 탐색하는 방법을 떠올릴 수 있다. 그러나 이렇게 ..

[백준] 2629번: 양팔저울

https://www.acmicpc.net/problem/2629 2629번: 양팔저울 첫째 줄에는 추의 개수가 자연수로 주어진다. 추의 개수는 30 이하이다. 둘째 줄에는 추의 무게들이 자연수로 가벼운 것부터 차례로 주어진다. 같은 무게의 추가 여러 개 있을 수도 있다. 추의 무 www.acmicpc.net 가능 여부를 확인해서 해결하는 dp 문제다. 1. 문제 조건 1) 양팔 저울의 왼쪽에 구슬이 있는데, 주어진 추를 사용해서 구슬의 무게를 잰다. 2) 추와 구슬의 무게가 주어졌을 때, 그 구슬의 무게를 잴 수 있는지 여부를 출력한다. 3) 추는 왼쪽 또는 오른쪽에 올릴 수 있다. 4) 추를 올리지 않을 수도 있다. 5) 추의 개수는 최대 30, 무게는 최대 500 이하의 자연수다. 2. dp 배열 ..

[백준] 1958번: LCS 3

https://www.acmicpc.net/problem/1958 1958번: LCS 3 첫 줄에는 첫 번째 문자열이, 둘째 줄에는 두 번째 문자열이, 셋째 줄에는 세 번째 문자열이 주어진다. 각 문자열은 알파벳 소문자로 이루어져 있고, 길이는 100보다 작거나 같다. www.acmicpc.net 문자열 3개의 LCS 길이를 구하는 dp 문제다. 1. 문제 조건 1) 문자열 3개의 LCS 길이를 출력한다. 2) 문자열은 알파벳 소문자로만 이루어져 있다. 3) 문자열의 길이는 100 이하다. 2. dp 배열 정의 문자열 2개의 LCS 길이를 구하는 dp 문제는 많이 풀어 봤다. 이 문제도 별로 다를 것 없이 문자열의 인덱스마다 LCS 길이를 저장하는 dp 배열을 만들어주면 된다. 문자열이 총 3개이므로 3..

[백준] 11066번: 파일 합치기

https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net 구간을 나누어 해결하는 dp 문제다. 1. 문제 조건 1) 전체 K장으로 이루어진 파일을 모두 합칠 때의 최소 비용을 출력한다. 2) 파일의 크기는 10,000 이하인 양의 정수다. 3) 파일 K1과 K2를 합치는 비용은 C1 + C2 이며, 합친 두 파일은 하나가 된다. 4) 위에서 합쳐진 파일의 비용은 C1 + C2 다. 2. dp 배열 정의 구간 [i, j] 의 파일들을 합친 최소 ..

[백준] 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차원 버전이다. 어려울 것 없이, 치즈버거와 감..