문제 링크 www.acmicpc.net/problem/1562 1562번: 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 백준 10844 - 쉬운 계단 수 문제에서 모든 수가 한 번 이상 포함되어야 한다는 조건이 추가되었습니다. 쉬운 계단 수와 전개는 똑같이 하되, 현재까지 나온 수들을 집합으로 관리해줍시다. 수의 길이가 n일 때 0번 ~ 9번까지의 모든 비트가 켜져있어야 합니다. 정답 코드 #include using namespace std; using ll = long long; const ll MOD = 1'000'000'000; ll d[(1
문제 링크 www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 (마지막 수 $\pm$ 1)의 방향으로 전개합니다. 길이가 $n$이 될 때까지 전개 가능하면 1을 리턴합니다. 0으로 시작하는 수는 없다는 것에 주의하세요. 해당 처리를 line 16 ~ 22에서 했습니다. 정답 코드 #include using namespace std; using ll = long long; int n; ll d[111][10]; const int MOD = 1'000'000'000; ll go(int l, int last) { if (last 9) return 0;..
문제 링크 www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 풀이 백준 1005 - ACM Craft랑 같은 문제입니다. (어떤 건물을 지을 수 있는 시간 최솟값 + 그 건물을 짓는데 걸리는 시간)이 다음 건물의 d값보다 크면 업데이트해줍니다. 정답 코드 #include using namespace std; using vi = vector; using vvi = vector; int n, cost[555], indeg[555], d[555]; vvi..
문제 링크 www.acmicpc.net/problem/1509 1509번: 팰린드롬 분할 세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다. 분할의 개수의 최솟값을 출력하 www.acmicpc.net 풀이 입력받은 문자열의 $i$번부터 끝까지 해당되는 부분 문자열을 s라 합시다. $d[i]$: $s$를 팰린드롬 분할했을 때 분할 개수의 최솟값. 각 문자열을 두 구간으로 나눠봅니다. $i$부터 시작하는 문자열 s에서 $u = (i$ ~ $j)$, $v = (j+1$ ~ $)$ 이렇게 두 구간으로 나눴을 때 $u$가 팰린드롬이면 $d..
문제 링크 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)$..
