문제 링크 www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 풀이 문자열 $s$의 양 끝이 같고, 그 사이 문자열이 팰린드롬이면 $s$도 팰린드롬입니다. 기저값으로 문자열 길이가 1이면 항상 팰린드롬, 길이가 2일땐 두 문자가 같으면 팰린드롬입니다. $d[i][j]$: 문자열 $s[i]$ ~ $s[j]$가 팰린드롬이면 1, 아니면 0 $d[i][j] = (s[i] == s[j])$ && $(d[i+1][j-1])$ 길이가 작은 값부터 채워나가면 됩니다. 정답 코드 #include using name..
문제 링크 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 풀이 보석이 N개, 가방이 K개 있습니다. 각 가방은 담을 수 있는 최대 무게가 정해져있고, 하나의 보석만을 담을 수 있습니다. 그리디하게 생각합시다. 최대 무게가 작은 가방부터 보며 그때 담을 수 있는 최대 가치의 보석을 털면 됩니다. 증명은 BOJ 채점기가 해주겠죠?? 자세한 구현은 코드를 참고해주세요. 정답 코드 #include #de..
문제 링크 www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 풀이 기본적인 유니온 파인드 문제입니다. 자세한 설명은 다른 블로그를 참고해주세요. 정답 코드 #include #define all(x) (x).begin(), (x).end() using namespace std; int n, m; int par[11'111]; struct Edge { int u, v, c; Edge(int u = 0, int v = ..
문제 링크 www.acmicpc.net/problem/1007 1007번: 벡터 매칭 평면 상에 N개의 점이 찍혀있고, 그 점을 집합 P라고 하자. 집합 P의 벡터 매칭은 벡터의 집합인데, 모든 벡터는 집합 P의 한 점에서 시작해서, 또 다른 점에서 끝나는 벡터의 집합이다. 또, P에 속 www.acmicpc.net 풀이 나이브하게 가능한 모든 벡터를 구한다고 생각해봅시다. 점을 두 개씩 짝지어 $\frac{N}{2}$개의 벡터를 만들고, 각 벡터마다 두 개의 방향이 존재합니다. 이는 $O(N*(N-2)*(N-4)*...*2*2)$정도 됩니다. 당연히 안 되겠죠. 조금 더 생각을 해봅시다. 어떤 두 점 $(x_1, y_1)$, $(x_2, y_2)$로 벡터를 만들면 $(x_1-x_2,\ y_1-y_2)$..