BAEKJOON/다이나믹 프로그래밍 (55) 썸네일형 리스트형 백준 2579번 [계단 오르기] (C++) -yes6686- 티스토리 백준 문제 풀이: 2579 [계단 오르기]문제 링크: https://www.acmicpc.net/problem/2579문제 설명:계단 오르기 게임에서 점수를 최대로 하기 위한 문제입니다. 계단은 한 번에 1칸 또는 2칸씩 오를 수 있으며, 연속된 세 개의 계단을 밟을 수 없습니다. 각 계단에는 점수가 주어지고, 마지막 계단은 반드시 밟아야 합니다.문제 해결 코드#include #include using namespace std;int arr[301]; // 각 계단의 점수int dp[301]; // 해당 계단까지의 최대 점수int main() { int n; // 계단의 개수 cin >> n; // 계단 점수 입력 for (int i = 1; i > arr[i]; } /.. 백준 2156번 [포도주 시식] (C++) -yes6686- 티스토리 백준 문제 풀이: 2156 [포도주 시식]문제 링크: https://www.acmicpc.net/problem/2156문제 설명:여러 잔의 포도주가 일렬로 나열되어 있고, 포도주를 마시는 규칙은 다음과 같습니다:포도주는 연속으로 세 잔을 마실 수 없습니다.각 포도주의 양이 주어질 때, 최대한 많은 양의 포도주를 마실 수 있는 값을 구합니다.문제 해결 코드#include #include using namespace std;int arr[10001]; // 각 포도주의 양int dp[10001]; // i번째 포도주까지 최대 마실 수 있는 포도주의 양int main() { ios::sync_with_stdio(false); cin.tie(NULL); int n; // 포도주 잔의 개수 .. 백준 14002번 [가장 긴 증가하는 부분 수열 4](C++) -yes6686- 티스토리 백준 문제 풀이: 14002 [가장 긴 증가하는 부분 수열 4]문제 링크: https://www.acmicpc.net/problem/14002문제 설명:주어진 수열에서 가장 긴 증가하는 부분 수열(LIS)의 길이를 구하고, 해당 수열을 출력하는 문제입니다.문제 해결 코드#include #include using namespace std;int arr[1001]; // 입력된 수열int dp[1001]; // LIS의 길이를 저장하는 배열stack s; // LIS를 역추적하여 저장하는 스택int main() { ios::sync_with_stdio(false); cin.tie(NULL); int n; // 수열의 크기 cin >> n; // 수열 입력 for (int .. 백준 2240번 [자두나무](C++) -yes6686- 티스토리 백준 문제 풀이: 2240 [자두나무]문제 링크: https://www.acmicpc.net/problem/2240문제 설명:자두나무 두 그루가 있고, 매초마다 1번 또는 2번 나무에서 자두가 떨어집니다. 자두를 받으려면 특정 나무 아래 있어야 하며, 최대 W번 다른 나무로 이동할 수 있습니다. T초 동안 받을 수 있는 최대 자두의 개수를 계산하는 문제입니다.문제 해결 코드#include #include using namespace std;int arr[1001]; // 자두가 떨어지는 나무 정보int dp[1001][31][3]; // dp[t][w][pos]: t초에 w번 이동 후 pos 나무 아래에 있을 때 최대 자두 개수int main() { ios::sync_wit.. 백준 10826번 [피보나치 수 4](C++) -yes6686- 티스토리 백준 문제 풀이: 10826 [피보나치 수 4]문제 링크: https://www.acmicpc.net/problem/10826문제 설명:피보나치 수열의 n번째 값을 계산하는 문제입니다. 단, n이 매우 커질 수 있으므로, 결과를 저장할 자료형으로 문자열을 사용해야 합니다.문제 해결 코드#include #include #include using namespace std;string dp[10001]; // 각 피보나치 수를 문자열로 저장// 두 문자열 숫자를 더하는 함수string sum(string a, string b) { string result = ""; int carry = 0; // 올림 수 // 문자열의 끝에서부터 더하기 while (a.size() || b.size()).. 백준 10844번 [쉬운 계단 수](C++) -yes6686- 티스토리 백준 문제 풀이: 10844 [쉬운 계단 수]문제 링크: https://www.acmicpc.net/problem/10844문제 설명:길이가 n인 계단 수를 계산하는 문제입니다. 계단 수는 각 자리 숫자가 인접한 자리와 1 차이가 나는 수를 말합니다. 예를 들어, 45656은 계단 수입니다.조건: 0으로 시작하는 숫자는 계단 수가 아닙니다. 결과는 1,000,000,000으로 나눈 나머지를 출력합니다.문제 해결 코드#include #define MOD 1000000000using namespace std;long long dp[101][10]; // dp[i][j]: 길이가 i이고 마지막 숫자가 j인 계단 수의 개수int main() { int n; cin >> n; // 초기값 설정 .. 백준 15486번 [퇴사 2](C++) -yes6686- 티스토리 백준 문제 풀이: 15486 [퇴사 2]문제 링크: https://www.acmicpc.net/problem/15486문제 설명:상담원이 N일 동안 각 날짜에 상담을 진행할 수 있는 경우, 최대 이익을 계산하는 문제입니다. 각 상담은 진행 기간과 이익이 주어지며, 기간이 초과되면 상담을 진행할 수 없습니다.문제 해결 코드#include #include using namespace std;int dp[1500001]; // dp[i]: i번째 날까지 최대 수익int main() { ios::sync_with_stdio(false); cin.tie(NULL); int n; cin >> n; int t, p; int maxAns = 0; for (int i = 1; i >.. 백준 11053번 [가장 긴 증가하는 부분 수열](C++) -yes6686- 티스토리 백준 문제 풀이: 11053 [가장 긴 증가하는 부분 수열]문제 링크: https://www.acmicpc.net/problem/11053문제 설명:주어진 배열에서 가장 긴 증가하는 부분 수열(LIS)의 길이를 구하는 문제입니다. 부분 수열은 배열의 원소 순서를 유지해야 합니다.문제 해결 코드#include #include using namespace std;int arr[1001]; // 입력된 배열int dp[1001]; // dp[i]: i번째 원소를 마지막으로 하는 LIS의 길이int main() { ios::sync_with_stdio(false); cin.tie(NULL); int n; cin >> n; for (int i = 0; i > arr[i]; .. 이전 1 2 3 4 5 6 7 다음
