BAEKJOON/다이나믹 프로그래밍 (55) 썸네일형 리스트형 백준 11055번 [가장 큰 증가하는 부분 수열](C++) -yes6686- 티스토리 백준 문제 풀이: 11055 [가장 큰 증가하는 부분 수열]문제 링크: https://www.acmicpc.net/problem/11055문제 설명:주어진 배열에서 증가하는 부분 수열의 합이 가장 큰 값을 구하는 문제입니다. 부분 수열은 배열의 원소 순서를 유지해야 합니다.문제 해결 코드#include #include using namespace std;int arr[1001]; // 입력된 배열int dp[1001]; // dp[i]: i번째 원소를 마지막으로 하는 증가하는 부분 수열의 최대 합int main() { ios::sync_with_stdio(false); cin.tie(NULL); int n; cin >> n; for (int i = 0; i > arr[i]; .. 백준 9461번 [파도반 수열](C++) -yes6686- 티스토리 백준 문제 풀이: 9461 [파도반 수열]문제 링크: https://www.acmicpc.net/problem/9461문제 설명:파도반 수열은 다음 점화식을 따릅니다:P(1) = 1, P(2) = 1, P(3) = 1P(n) = P(n-1) + P(n-5) (n ≥ 4)여러 개의 테스트 케이스에서 주어진 n에 대해 P(n)을 계산하는 문제입니다.문제 해결 코드#include using namespace std;long long dp[101]; // 파도반 수열 값 저장int main() { int T; cin >> T; // 초기값 설정 dp[1] = 1; dp[2] = 1; dp[3] = 1; dp[4] = 2; // 점화식에 따라 나머지 값 계산 for.. 백준 2482번 [색상환](C++) -yes6686- 티스토리 백준 문제 풀이: 2482 [색상환]문제 링크: https://www.acmicpc.net/problem/2482문제 설명:색상환에 색상 N개가 원형으로 배치되어 있습니다. 이 중 K개의 색상을 고르려 합니다. 단, 인접한 색은 동시에 선택할 수 없습니다. 가능한 경우의 수를 구하는 문제입니다. 결과는 1,000,000,003으로 나눈 나머지를 출력합니다.문제 해결 코드#include #define MOD 1000000003 using namespace std;int dp[1001][1001];int main() { ios::sync_with_stdio(false); cin.tie(NULL); int n, k; cin >> n >> k; // DP 초기화 for (.. 백준 1912번 [연속합](C++) -yes6686- 티스토리 백준 문제 풀이: 1912 [연속합]문제 링크: https://www.acmicpc.net/problem/1912문제 설명:N개의 정수로 이루어진 배열에서 연속된 부분 배열의 합이 최대가 되는 값을 구하는 문제입니다. 모든 수가 음수인 경우도 고려해야 합니다.문제 해결 코드#include using namespace std;int arr[100001];int main() { ios::sync_with_stdio(false); cin.tie(NULL); int n; cin >> n; int isAllNegative = 1; int maxAns = -1001; // 입력값 처리 및 초기 최대값 계산 for (int i = 0; i > arr[i]; if.. 백준 2193번 [이친수](C++) -yes6686- 티스토리 백준 문제 풀이: 2193 [이친수]문제 링크: https://www.acmicpc.net/problem/2193문제 설명:이친수는 다음과 같은 조건을 만족하는 이진수입니다:0으로 시작하지 않습니다.1이 두 번 연속으로 나타나지 않습니다.정수 N(1 ≤ N ≤ 90)이 주어졌을 때, N자리 이친수의 개수를 구하는 문제입니다.문제 해결 코드#include using namespace std;long long dp[91]; // dp[i]: i자리 이친수의 개수int main() { int n; cin >> n; // 초기값 설정 dp[1] = 1; // 1자리 이친수: "1" dp[2] = 1; // 2자리 이친수: "10" // 점화식 계산 for (int i = 3.. 백준 1932번 [정수 삼각형](C++)-yes6686- 티스토리 백준 문제 풀이: 1932 [정수 삼각형]문제 링크: https://www.acmicpc.net/problem/1932문제 설명:정수 삼각형이 주어졌을 때, 맨 위층에서 시작하여 아래층으로 내려오며 선택된 숫자의 합이 최대가 되는 경로를 구하는 문제입니다. 각 층에서 선택된 숫자는 바로 아래층의 인접한 숫자로만 이동할 수 있습니다.문제 해결 코드#include using namespace std;int arr[501][501];int dp[501][501];int main() { int n; cin >> n; // 삼각형 배열 입력 for (int i = 0; i > arr[i][j]; } } // DP 초기화 및 계산 dp[0][0] = arr[0][0.. 백준 4883번 [삼각 그래프](C++)-yes6686- 티스토리 백준 문제 풀이: 4883 [삼각 그래프]문제 링크: https://www.acmicpc.net/problem/4883문제 설명:삼각 그래프가 주어질 때, 왼쪽 상단에서 시작하여 오른쪽 하단으로 이동하는 최소 비용을 계산하는 문제입니다. 이동은 다음과 같은 규칙을 따릅니다:현재 위치에서 바로 아래, 아래 왼쪽 대각선, 아래 오른쪽 대각선으로 이동 가능그래프의 각 노드에는 비용이 적혀 있으며, 이동한 노드의 비용을 합산문제 해결 코드#include #include using namespace std;long long arr[100001][3];long long dp[100001][3];int main() { ios::sync_with_stdio(false); cin.tie(NULL); in.. 백준 1003번 [피보나치 함수](C++)-yes6686- 티스토리 백준 문제 풀이: 1003 [피보나치 함수]문제 링크: https://www.acmicpc.net/problem/1003문제 설명:피보나치 수열에서 \( F(0) = 0 \), \( F(1) = 1 \), \( F(n) = F(n-1) + F(n-2) \)로 정의됩니다. 이때 \( F(n) \)을 계산할 때 호출되는 0과 1의 개수를 구하는 문제입니다.문제 해결 코드#include using namespace std;long long int zeroCntDp[41];long long int oneCntDp[41];// 0이 호출된 횟수 계산long long int zeroCntFibo(int n) { if (zeroCntDp[n] != -1) return zeroCntDp[n]; if (n =.. 이전 1 ··· 3 4 5 6 7 다음
