목록2024/02 (147)
득이공간
[백준 C++] 11660 구간 합 구하기 5 - 다이나믹프로그래밍
11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net #include using namespace std; int DP[1025][1025]; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int N, M; cin >> N >> M; for (int i = 1; i Number; DP[i][j] = DP[i][j - 1] + DP[i - 1][j] - DP[i - 1][j - 1] + Num..
[백준 C++] 9465 스티커 - 다이나믹프로그래밍
9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net #include using namespace std; int ST[2][100000]; int DP[2][100000]; void Test() { int N; cin >> N; for (int i = 0; i > ST[i][j]; } } if (N
[백준 C++] 1932 정수 삼각형 - 다이나믹프로그래밍
1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net #include using namespace std; int Triangle[501][501]; int DP[501][501]; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int N; cin >> N; cin >> Triangle[1][1]; DP[1][1] = Triangle[1][1]; int Max = DP[1][1]; for (int i = 2; i Triangle[i][j]; if (j == 1) { DP[i][j] = DP[i - 1][..
[백준 C++] 1629 곱셈 - 분할정복
1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net #include using namespace std; int A, C; long long BinaryFunction(int B) { if (B == 0) { return 1; } else if (B == 1) { return A % C; } if (B % 2 == 0) { return BinaryFunction(B / 2) * BinaryFunction(B / 2) % C; } else { return BinaryFunction(B / 2) * BinaryFunction(B / 2 + 1) % C; } } int main() ..
[백준 C++] 1149 RGB거리 - 다이나믹프로그래밍
1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net #include using namespace std; int Weight[1001][3]; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int N; cin >> N; int R, G, B; cin >> R >> G >> B; Weight[1][0] = R; Weight[1][1] = G; Weight[1][2] = B; for (int i = 2; i > ..
[백준 C++] 16953 A → B - 너비우선탐색
16953번: A → B 첫째 줄에 A, B (1 ≤ A End) { con..
[백준 C++] 11725 트리의 부모 찾기 - 너비우선탐색
11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net #include #include #include using namespace std; int N; int Parent[100001]; bool Visited[100001]; list Neighbors[100001]; queue SearchQueue; void BFS(int Root) { SearchQueue.emplace(Root); while (!SearchQueue.empty()) { int Current = SearchQueue.front(); SearchQueue.pop(); if (Visited[Current]) { ..
[백준 C++] 11053 가장 긴 증가하는 부분 수열 - 다이나믹프로그래밍
11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net #include using namespace std; int Sequence[1000]; int Length[1000]; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int MaxLength = 0; int N; cin >> N; for (int i = 0; i > Seq..
[백준 C++] 15654 N과 M (5) - 백트래킹
15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net #include #include #include #include using namespace std; int N, M; vector Numbers; void DFS(int Sequence[], int Index, bool Visited[]) { if (Index == M) { for (int i = 0; i M; Numbers.reserve(N); for (int i = 0; i < N; ++i) { int Number;..
[백준 C++] 15650 N과 M (2) - 백트래킹
15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net #include using namespace std; int N, M; void DFS(int Sequence[], int Index, int Number) { if (Index == M) { for (int i = 0; i < M; ++i) { cout M; int Sequence[8]; DFS(Sequence, 0, 1); } DFS & 백트래킹을 이용해서 푸는 문제입니다. 1부터 N까지 각 숫자를 고를 때와 안 고를 때를 DFS로 탐색하도록 하고, 현재 숫..