김머성 블로그

[BAE/<JOON> 문제풀이] 1461. 도서관

https://www.acmicpc.net/problem/1461 1461번: 도서관 첫째 줄에 책의 개수 N과, 세준이가 한 번에 들 수 있는 책의 개수 M이 주어진다. 둘째 줄에는 책의 위치가 주어진다. N은 10,000보다 작거나 같은 자연수이고, M은 10,000보다 작거나 같다. 책의 위치 www.acmicpc.net 핵심:: m권의 책을 한번에 옮길 수 있고 멀리있는 책부터 복구 시키면 총 m권의 책을 복구하는데 { max(m) * 2 } 의 비용이 든다. 또한 복구를 완료하면 0 으로 돌아올 필요가 없으므로 마지막 m권의 책을 복구하는데에는 { max(m) } 의 비용이 든다. 풀이:: 멀리있는 책일 수록 비용이 늘어나고 연속된 m권에 대해서는 가장 멀리있는 책의 비용만 지불할 수 있으므로 ..

[BAE/<JOON> 문제풀이] 1987. 알파벳

www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 풀이 생략 더보기 #include using namespace std; int arr[21][21]; int ch[21][21]; int n, m; int chc[26]; int mx = -2100000000; void r(int x, int y, int cnt) { if (x n || y m) return; if (chc[arr[x][y]] == 1 || ch[x..

[BAE/<JOON> 문제풀이] 1509. 팰린드롬 분할

www.acmicpc.net/problem/1509 1509번: 팰린드롬 분할 세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다. 분할의 개수의 최솟값을 출력하 www.acmicpc.net Manacher's 알고리즘을 사용해 문자열 내부에 있는 모든 팰린드롬의 길이를 구할 수 있다. 최소 분할 수를 구하는 점화식은 다음과 같다. 현재 위치 팰린드롬 길이 k에 대해서 dp[i] = min(dp[i - 1] + 1, dp[i]) -> 현재 위치의 팰린드롬을 사용하는 것보다 사용하지 않는 것이 더 짧은 경우 for(1 ~ k = j)..

[BAE/<JOON> 문제풀이] 1202. 보석 도둑

www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 각각의 가방마다 최대 한개의 보석만 넣을 수 있으므로 보석들을 가치순으로 정렬하고 해당 보석을 넣을 수 있는 가장 작은 가방에 넣는 식으로 구현했다. 이런 방식으로 구현하면 vector 대신 multiset을 사용해야 시간 초과를 피할 수 있다. 처음에 vector.erase 메서드 인자를 지우는 원소의 인덱스를 받길래 상수시간에 실행될 것이라고 생각..

[BAE/<JOON> 문제풀이] 20040. 사이클 게임

www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 간선이 추가 될 때마다 부모를 추적하고 같은 부모를 가진다면 해당 간선번호를 출력한다. 더보기 #include #include using namespace std; int parent[500001]; int findp(int x) { if (parent[x] == x) return x; return parent[x] = findp(parent[x]); } struct node { int s, e; }; i..

[BAE/<JOON> 문제풀이] 1647. 도시 분할 계획

www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수N, 길의 개수M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 집 www.acmicpc.net 주어진 간선으로 MST를 구성하고 그 간선내의 가장 큰 간산 하나를 제거하면 정답을 얻을 수 있다 더보기 #include #include #include using namespace std; struct h { int x, y, v; }; bool cmp(h a, h b) { return a.v < b.v; } int parent[100001]; int findp(int x..