[백준] 17526번: Star Trek

https://www.acmicpc.net/problem/17526 17526번: Star Trek Your program is to read from standard input. The input starts with a line containing an integer, n (3 ≤ n ≤ 100,000), where n is the number of planets of UFP. The planets are numbered from 1 to n. The next line consists of n − 1 integers, where the www.acmicpc.net 1. 문제 조건 1) $N$개의 행성이 있는데, 1번부터 $N$번까지 순서대로 한 줄로 이어져 있다. 2) 1번 행성에서 우주선을 타고 $..

[백준] 14240번: 부분 수열의 점수

https://www.acmicpc.net/problem/14240 14240번: 부분 수열의 점수 수열 s = s1, s2, ..., sn의 점수는 Σi·si로 구할 수 있다. 수열 s의 연속된 부분 수열의 점수의 최댓값을 구하는 프로그램을 작성하시오. www.acmicpc.net 1. 문제 조건 1) 수열 $s = s_{1}, s_{2}, ..., s_{n}$ 의 점수는 $\sum_{i=1}^n (i \times s_{i})$ 이다. 2) 수얼 $s$의 연속된 부분 수열의 점수 중 최댓값을 출력한다. 2. 문제 접근 생각보다 문제가 짧다. 연속된 부분 수열로 점수를 계산할 수 있고, 부분 수열의 값에 그 인덱스를 곱한 값을 모두 더하면 점수가 계산된다. 어떤 구간을 부분 수열로 잡는지에 따라 곱해지는..

[백준] 6171번: 땅따먹기

https://www.acmicpc.net/problem/6171 6171번: 땅따먹기 (1) / (4) / (2, 3) 으로 땅을 묶어 사보자. 상헌이는 100 * 1 + 20 * 15 + 1 * 100 = 500의 가격에 땅을 살 수 있다. www.acmicpc.net 1. 문제 조건 1) $N$개의 땅이 있는데, 각 땅은 $W_{i} \times H_{i}$ 크기의 직사각형 모양이다. 2) 땅 하나의 가격은 $W_{i} \times H_{i}$ 이다. 3) 땅 여러 개를 묶어서 살 수도 있는데, 그 때의 가격은 $\max (W_{i}) \times \max (H_{i})$ 이다. 4) 땅 전체를 살 때의 최소 비용을 출력한다. 2. 문제 접근 전체 땅 조합을 모두 확인하기에는 시간 초과가 날 것이 ..

[백준] 4008번: 특공대

https://www.acmicpc.net/problem/4008 4008번: 특공대 입력은 세 줄로 구성된다. 첫 번째 줄에 전체 병사들 수인 양의 정수 n이 주어진다. 두 번째 줄에 특공대의 조정된 전투력 계산 등식의 계수인 세 정수 a, b, c가 주어진다. 마지막 줄에 병사들 1, 2, www.acmicpc.net 1. 문제 조건 1) $N$명의 병사가 있는데, 각 병사의 전투력은 $x_{i}$이다. $(1 \leq i \leq N)$ 2) 연속된 번호의 병사를 묶어서 특공대를 만든다. 3) 특공대의 전투력 $x$는 포함된 병사들의 전투력 합이다. $(x = x_{i} + x_{i+1} + ... + x_{k})$ 4) 조정된 특공대의 전투력 $x'$은 다음 식을 따른다. $x' = ax^{2} ..

[백준] 13263번: 나무 자르기

https://www.acmicpc.net/problem/13263 13263번: 나무 자르기 첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 둘째 줄에는 a1, a2, ..., an이, 셋째 줄에는 b1, b2, ..., bn이 주어진다. (1 ≤ ai ≤ 109, 0 ≤ bi ≤ 109) a1 = 1이고, bn = 0이며, a1 b2 > ... > bn을 만족 www.acmicpc.net 1. 문제 조건 1) 나무 N 개를 모두 잘라야 한다. 2) 전기톱을 한 번 사용하면, 그 나무의 높이는 1 줄어든다. 3) 전기톱을 사용할 때마다 전기톱을 충전해야 한다. 4) 충전 비용은 높이가 0이 된 나무 중 가장 큰 번호에 해당하는 비용이다. 5) 모든 나무를..

[백준] 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] 의 파일들을 합친 최소 ..