문제 링크 www.acmicpc.net/problem/13544 13544번: 수열과 쿼리 3 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. i j k: Ai, Ai+1, ..., Aj로 이루어진 부분 수열 중에서 k보다 큰 원소의 개수를 출력한다. www.acmicpc.net 풀이 예전에 Persistent Segment Tree 연습한다고 풀었던 문젠데, 이번엔 Merge Sort Tree를 연습한다고 풀어보게 되었습니다. 머지 소트 트리는 트리의 각 노드마다 항상 아래 두 노드의 리스트를 정렬된 상태로 갖고 있도록 저장하는 세그먼트 트리입니다. PST는 개념상 2차원 세그먼트 트리인데, 공간 효율을 높인 세그먼트 트리라고 보시면 됩니다..
문제 링크 www.acmicpc.net/problem/2616 2616번: 소형기관차 첫째 줄에 기관차가 끌고 가던 객차의 수가 입력된다. 그 수는 50,000 이하이다. 둘째 줄에는 기관차가 끌고 가던 객차에 타고 있는 손님의 수가 1번 객차부터 차례로 입력된다. 한 객차에 타고 있 www.acmicpc.net 풀이 3대의 기관차가 항상 같은 수의 객차를 끌게 됩니다. 결국 N개중 3개의 시작점을 골라 최댓값을 뽑는 문제라고 생각할 수 있습니다. 기관차가 끌 수 있는 객차의 수만큼 구간을 잡고, 그 합을 미리 계산해두면 편하게 구현할 수 있습니다. 정답 코드 #include using namespace std; int d[55'555][3]; int n, k, p[55'555], sum[55'555];..
문제 링크 www.acmicpc.net/problem/2169 2169번: 로봇 조종하기 첫째 줄에 N, M(1≤N, M≤1,000)이 주어진다. 다음 N개의 줄에는 M개의 수로 배열이 주어진다. 배열의 각 수는 절댓값이 100을 넘지 않는 정수이다. 이 값은 그 지역의 가치를 나타낸다. www.acmicpc.net 풀이 일반적인 DP이지만 방향을 잘 잡아주어야 합니다. 저 같은 경우 어느 방향에서 왔는지에 대한 정보를 함께 넘겨주어, 그 방향으로는 다시 전개를 안 하게끔 구현했습니다. (line 20) 정답 코드 #include #define INF 0x3f3f3f3f using namespace std; int n, m, p[1111][1111]; int dx[] = {0, 1, 0}, dy[] = ..
문제 링크 www.acmicpc.net/problem/2281 2281번: 데스노트 첫째 줄에 n(1 ≤ n ≤ 1,000), m(1 ≤ m ≤ 1,000)이 주어진다. m은 노트의 가로 칸의 개수(폭, 너비)이다. 다음 n개의 줄에는 각 사람의 이름의 길이가 노트에 적어야 할 순서대로 주어진다. 각 길이는 m www.acmicpc.net 풀이 이름들을 순서대로 그룹 지어준다고 생각해봅시다. 각 그룹 값의 합의 상한은 노트의 폭과 같고, 그룹의 값은 (그룹에 포함된 이름의 길이 합 + [이름 개수] - 1)입니다. 간단한 DP로 풀 수 있습니다. $D[i]$: 그룹이 $i$번 이름으로 시작하고, 그 뒤의 모든 이름을 적절히 그룹으로 묶어주었을 때 남는 칸의 수의 제곱의 합의 최솟값 $[i], [i, i+..
문제 링크 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..
문제 링크 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])$ 단,..