[백준] 26608번: 캠핑하기

https://www.acmicpc.net/problem/26608 26608번: 캠핑하기 $M$줄에 걸쳐 $i$번째 줄에 날씨가 안 좋은 정도가 $i$일때 걸리는 시간 당 만족도의 최댓값을 값이 $0$일 경우 $0/0$으로, 아닌 경우 $p/q$ ($p$는 정수, $q$는 양의 정수, $\gcd(p ,q)=1$)꼴로 출력한다. www.acmicpc.net 1. 문제 조건 1) $N$개의 캠핑장이 있다. 2) $i$번째 캠핑장까지 가는 데에 걸리는 시간은 $A_{i}$ 이다. 3) $i$번째 캠핑장에 갔을 때의 만족도는 $B_{i}$이다. 4) 날씨 계수 $k$가 주어진다. 5) 날씨가 안 좋은 정도는 $x$로 표현되며 1 이상 $M$ 이하의 정수다. 6) 모든 날씨 상황에 대해 $\frac{B_{i} ..

[백준] 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번 행성에서 우주선을 타고 $..

[백준] 12795번: 반평면 땅따먹기

https://www.acmicpc.net/problem/12795 12795번: 반평면 땅따먹기 첫 줄에는 게임을 진행한 정보의 개수 Q(1 ≤ Q ≤ 200,000)이 주어지며, 이어서 Q 줄에 걸쳐 각 정보가 주어진다. 각 줄의 첫 번째 숫자가 1일 경우 이어서 2개의 정수 a, b(|a| ≤ 1,000,000, |b| ≤ 1,000,000, www.acmicpc.net 1. 문제 조건 1) 쿼리가 1로 시작하는 경우, $y = ax + b$ 꼴의 1차 함수가 추가된다. 2) 주어진 직선의 아래쪽을 점령한다. 3) 쿼리가 2로 시작하는 경우, 점령한 영역 중 주어진 $x$에서 $y$의 최댓값을 출력한다. 2. 문제 접근 전형적인 Convex Hull Trick 문제다. 최대 200,000개의 직선이..

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

[백준] 23282번: Line Fighter 2

https://www.acmicpc.net/problem/23282 23282번: Line Fighter 2 첫째 줄에 직선의 개수 N과 질문의 개수 Q가 주어진다. N은 1이상 100,000이하의 정수이고, Q는 0이상 100,000이하의 정수이다. 그 다음부터 N줄에 걸쳐 각 직선의 정보가 주어진다. 각 직선을 y = ax+b로 www.acmicpc.net 1. 문제 조건 1) 2차원 평면 상에 1차 함수 $N$개가 주어진다. 2) 기울기 $a$와 $y$ 절편 $b$ 가 주어진다. 3) $x$ 값이 주어잘 때, 직선 $N$개 중에 $x$에 대한 최댓값 혹은 최솟값을 출력한다. 4) 직선의 개수 $N$은 최대 100,000, 쿼리의 개수 $M$은 최대 100,000 이다. 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) 모든 나무를..