문제 링크 www.acmicpc.net/problem/2306 2306번: 유전자 DNA 서열은 4개의 문자 {a,c,g,t} 로 이루어진 문자열이다. DNA 서열에는 생명의 신비를 풀 수 있는 많은 정보가 들어 있다. 특히 KOI 유전자의 길이는 사람의 키와 깊은 상관 관계가 있다는 것이 알려 www.acmicpc.net 풀이 DP 문제입니다. 상태를 다음과 같이 정의합시다. $D[i][j]$: 부분 문자열 $s[i, j]$의 최대 KOI 유전자 길이 1) 우선 간단하게 $i$이상 $j$미만의 모든 $k$에 대해, $$D[i][j] = \max_{k=i}^{j-1}(D[i][k] + D[k+1][j])$$ 이런 방식으로 i ~ j를 가능한 모든 두 구간으로 나누어보면 최댓값을 구할 수 있습니다. 2) ..
문제 링크 www.acmicpc.net/problem/12886 12886번: 돌 그룹 오늘 강호는 돌을 이용해 재미있는 게임을 하려고 한다. 먼저, 돌 세개는 그룹으로 나누어져 있으며 각각의 그룹에는 돌이 A, B, C개가 있다. 강호는 모든 그룹에 있는 돌의 개수를 같게 만들려고 www.acmicpc.net 풀이 간단한 DP 문제입니다. 각 돌 그룹의 돌 개수를 상태로 하여 전개해줍시다. 주의할 점은 그룹당 가능한 돌의 개수가 1500개입니다. $O(1500^3)$으로 공간을 잡으면 메모리가 터지는데, 모든 돌의 개수는 항상 일정하다는 것을 생각하여 두 그룹의 돌 개수만 상태로 관리해도 괜찮습니다. 정답 코드 #include #define all(x) (x).begin(), (x).end() usin..
문제 링크 www.acmicpc.net/problem/10800 10800번: 컬러볼 첫 줄에는 공의 개수를 나타내는 자연수 N이 주어진다(1 ≤ N ≤ 200,000). 다음 N개의 줄 중 i번째 줄에는 i번째 공의 색을 나타내는 자연수 Ci와 그 크기를 나타내는 자연수 Si가 주어진다(1 ≤ Ci ≤ N www.acmicpc.net 풀이 구현 문제라 사실상 코드 설명이 되겠습니다. 1) 모든 공들을 크기순으로 정렬해줍니다. (코드상 $p$ 벡터) 2) 각 색별로 공들의 사이즈를 오름차순으로 저장해줍니다. (코드상 $cnt$ 벡터) 3) 모든 공을 순회하며, 자신보다 작은 사이즈 공 중(이전에 순회한 공들), 같은 색의 공을 제외한 나머지 사이즈합을 정답에 추가해줍시다. 정답 코드 #include #d..
링크 codeforces.com/contest/1497 Dashboard - Codeforces Round #708 (Div. 2) - Codeforces codeforces.com 이번 대회는 중간에 서버가 터져서 unrated 되었다. 망했었는데 너무 다행이다.. 이제부터 참가한 라운드를 업솔빙하기로 했다. Problem Set 기준 난이도가 2000 이하인 문제까지는 다시 풀어보려고 한다. A번: 제출시간 00:11 풀이 자체는 문제 해석을 끝내자마자 떠올렸다. 각 원소를 오름차순으로 중복되지 않게 한 번씩 출력한 뒤, 나머지는 뒤에 마음대로 출력하면 된다. 근데 내가 unique() 함수를 잘못 알고 있어 구현이 좀 오래 걸렸다. 보통 벡터에서 중복된 원소를 제거할 때 v.erase(unique(..
문제 링크 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 - (..