본문 바로가기
728x90
SMALL

BAEKJOON/다이나믹 프로그래밍

 (49)
백준 2302번 [극장 좌석](C++) -yes6686- 티스토리 백준 문제 풀이: 2302 [극장 좌석]문제 링크: https://www.acmicpc.net/problem/2302문제 설명:극장 좌석이 한 줄로 배치되어 있고, 특정 좌석은 VIP로 고정되어 있어 자리를 바꿀 수 없습니다. 나머지 좌석은 자유롭게 배치할 수 있으며, 극장 좌석의 배치 방법의 가짓수를 계산하는 문제입니다.VIP 좌석은 고정되어 이동할 수 없습니다.인접한 두 좌석을 서로 바꾸는 방식으로 자유 좌석의 배치를 다양하게 구성할 수 있습니다.문제 해결 코드#include using namespace std;int dp[41]; // DP 배열: 각 구간의 좌석 배치 방법의 가짓수를 저장int main() { ios::sync_with_stdio(false); cin.tie(NULL);..
백준 15988번 [1, 2, 3 더하기 3](C++) -yes6686- 티스토리 백준 문제 풀이: 15988 [1, 2, 3 더하기 3]문제 링크: https://www.acmicpc.net/problem/15988문제 설명:정수 N을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 문제입니다. 결과는 1,000,000,009로 나눈 나머지를 출력해야 합니다.예를 들어, N=4일 때 가능한 방법은 다음과 같습니다: 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2, 1+3, 3+1 (총 7가지).동적 프로그래밍을 활용해 효율적으로 풀이합니다.문제 해결 코드#include #define MOD 1000000009#define MAX 1000001using namespace std;long long int dp[MAX]; // 각 숫자를 1, 2, 3의 합으로 나타내는 경..
백준 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; // 초기값 설정 ..
728x90
LIST

티스토리툴바