문제 링크 www.acmicpc.net/problem/1424 1424번: 새 앨범 첫째 줄에 노래의 개수 N이 주어진다. 이 값은 100,000보다 작거나 같은 자연수이다. 둘째 줄에는 노래의 길이 L이 주어진다. 이 값은 초 단위이다. 셋째 줄에는 한 시디의 용량 C가 초 단위로 주어 www.acmicpc.net 풀이 시디에 들어가는 곡의 수가 13의 배수이면 안된다는 조건 때문에 생각없이 풀면 여러번 틀릴 수 있는 문제입니다. 우선 한 시디에 들어갈 수 있는 곡의 수 $k$의 최댓값을 구해봅시다. 노래 한 곡을 추가할 때마다 1초의 시간을 사이에 끼워야합니다. 노래의 길이 $l$, CD의 용량 $c$에 대해, $k$는 다음 부등식을 만족합니다. $l + (k-1)(l+1) \leq c$ $k(l+1..
문제 링크 www.acmicpc.net/problem/1670 1670번: 정상 회담 2 첫째 줄에 정상 회담에 참가한 사람의 수 N이 주어진다. 이 값은 10,000보다 작거나 같은 짝수이다. www.acmicpc.net 풀이 백준 17268 - 미팅의 저주 문제와 입력도, 출력도, 코드도 똑같습니다. 카탈란 수를 구해주면 됩니다. 정답 코드 #include #include using namespace std; using ll = long long; #define MOD 987654321LL ll d[5001] = { 1 }; int n; int main() { cin >> n; n /= 2; for (int i = 1; i < n + 1; i++) { for (int j = 0; j < i; j++)..
문제 링크 www.acmicpc.net/problem/2186 2186번: 문자판 첫째 줄에 N(1 ≤ N ≤ 100), M(1 ≤ M ≤ 100), K(1 ≤ K ≤ 5)가 주어진다. 다음 N개의 줄에는 M개의 알파벳 대문자가 주어지는데, 이는 N×M 크기의 문자판을 나타낸다. 다음 줄에는 1자 이상 80자 이하의 www.acmicpc.net 풀이 상태 전개는 DFS로 해도, BFS로 해도 관계없습니다. 위치와 레벨만 잘 고려해준다면요. DP 배열을 다음과 같이 정의합시다. $\text{D}[x][y][l]$: $(x, y)$칸을 $l$번째 문자로 방문했을 때 가능한 경우의 수 값은 다음처럼 채울 수 있습니다. $\text{D}[x][y][l] = \text{sum(D}[x'][y'][l-1])$ 단,..
문제 링크 www.acmicpc.net/problem/2698 2698번: 인접한 비트의 개수 첫째 줄에 테스트 케이스의 수 T(1 ≤ T ≤ 1,000)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 수 2개가 공백으로 구분되어 이루어져 있다. 첫 번째 수는 n이고, 두 번째 수는 k이다. n과 www.acmicpc.net 풀이 $\text{D}[i][j][\text{cnt}]$: $i$번째 비트가 $j$이고, 그때 남은 인접한 비트의 수가 $cnt$일 때 조건을 만족하는 수열의 개수 $j$는 $0$ 또는 $1$입니다. 다음과 같이 전개될 수 있습니다. $$\text{D}[i][j][\text{cnt}] = \text{D}[i+1][0][\text{cnt}] + \begin{cases}\te..
문제 링크 www.acmicpc.net/problem/2159 2159번: 케익 배달 첫째 줄에 N이 주어지고 둘째 줄에는 선아가 일하는 레스토랑의 위치가, 셋째 줄부터는 N명의 위치가 X와 Y로 주어진다. 두 좌표 사이에는 공백이 하나 이상 있다. (1 ≤ N, X, Y ≤ 100,000) www.acmicpc.net 풀이 각 주문마다 해당되는 칸과 인접한 4칸, 총 5칸을 갈 수 있는 상태로 정의합니다. 주문과 주문 사이 갈 수 있는 5*5가지 경우의 수로 모두 전이해주면 됩니다. 정답 코드 #include #define INF 0x3f3f3f3f3f3f3f3fLL #define ft first #define sd second using namespace std; using ll = long long..
문제 링크 www.acmicpc.net/problem/16287 16287번: Parcel 입력은 표준입력을 사용한다. 입력의 첫 줄에는 무게 w(10 ≤ w ≤ 799,994)와 A의 원소 개수 n(4 ≤ n ≤ 5,000)이 공백으로 분리되어 주어진다. 다음 줄에는 A의 원소인 n개의 정수 ai ∈ A(1 ≤ i ≤ n)가 www.acmicpc.net 풀이 이번 문제는 카테고리를 너무 의식한 나머지 오래 걸렸던 문제입니다. 사실 크게 보면 DP가 맞긴 한데 일반적으로 생각하는 그런 DP는 아녔습니다. 일단 4개를 한 번에 고르는 경우의 수는 너무 많으니 두 개, 두 개씩 골라 합을 비교하는 방식으로 갑시다. $a_i + a_j + a_k + a_l = W$ 위의 식을 $a_i + a_j = W - (..
문제 링크 www.acmicpc.net/problem/1019 1019번: 책 페이지 첫째 줄에 0이 총 몇 번 나오는지, 1이 총 몇 번 나오는지, ..., 9가 총 몇 번 나오는지를 공백으로 구분해 출력한다. www.acmicpc.net 풀이 눈물 줄줄 흘리면서 풀었습니다 ㄹㅇ 이거 제 기준으론 골드 아닙니다.. 아마 더 쉬운 방법으로 구현하거나 규칙을 찾을 수 있을듯한데 그거 생각하는 것만 해도 골드는 아닌 것 같습니다. 백준 9527 - 1의 개수 세기 저는 위 문제와 유사한 방법으로 풀었습니다. 차이점은 2진수가 아니라 10진수고, 0의 개수까지 세주어야 해서 사고 회로가 터져나갑니다. 어쨌든 정답을 구하는 근본 논리는 위 문제와 같습니다. 해당 글을 먼저 참고해주세요. 누적합 배열을 정의해봅시..
문제 링크 www.acmicpc.net/problem/2618 2618번: 경찰차 첫째 줄에는 동서방향 도로의 개수를 나타내는 정수 N(5≤N≤1,000)이 주어진다. 둘째 줄에는 처리해야 하는 사건의 개수를 나타내는 정수 W(1≤W≤1,000)가 주어진다. 셋째 줄부터 (W+2)번째 줄까지 www.acmicpc.net 풀이 저는 경로 추적이 생각보다 까다롭게 느껴졌습니다. 1번, 2번 경찰차가 각각 몇번 사건을 해결했는지를 상태로 둡시다. $i$번 사건을 1번, 2번 경찰차가 해결하는 각 경우에 대해, (경찰차의 마지막 위치 ~ $i$번 사건이 일어난 곳의 위치) 사이 거리를 더해주며 최솟값을 갱신하면 됩니다. 경로추적은 의외로 간단합니다. 발생한 사건을 순서대로 보며, $i$번 사건을 1번 경찰차가 ..
문제 링크 www.acmicpc.net/problem/1006 1006번: 습격자 초라기 하나의 특수 소대로 인접한 두 영역을 커버할 수 있는 배치는 (2,10), (9,16), (4,5), (7,8), (13,14) 이다. 그리고 나머지 6개 구역은 각각 하나의 특수 소대로 커버할 수 있다. 그러므로 최소 11개 특수 소 www.acmicpc.net 풀이 눈물겹게 풀었습니다... 😢😢😢 $i$번 칸의 위아래 각각 1) 선택하지 않음(앞에서 오른쪽 칸을 먹은 상태) 2) 한 칸만 선택 3) 오른쪽과 함께 선택 의 3*3가지 상태와 $i$번의 위, 아래칸을 함께 선택하는 상태로 총 10가지 경우가 있습니다. 각 상태에 따라 어떤 상태로 전이할지 정해주고 DP를 돌리면 됩니다. 맵이 원형이므로 첫 칸에서 가..