BAEKJOON/다이나믹 프로그래밍 (49) 썸네일형 리스트형 백준 9655번 [돌 게임](C++) -yes6686- 티스토리 백준 문제 풀이: 9655 (돌 게임)문제 링크: https://www.acmicpc.net/problem/9655문제 설명:돌 게임은 돌을 1개 또는 3개 가져갈 수 있는 게임입니다. 두 사람이 번갈아가며 게임을 진행하며, 마지막 돌을 가져가는 사람이 승리합니다. 주어진 돌의 개수 n에 대해, 시작하는 사람이 이길 수 있는지 확인하여 이긴 사람을 출력합니다. - "SK"는 상근이가 승리, "CY"는 창영이가 승리입니다.문제 해결 코드#include using namespace std;int dp[1001]; // dp[i]: 돌이 i개 남았을 때 이긴 사람 (1: SK, 2: CY)int main() { int n; cin >> n; dp[1] = 1; // 돌 1개: SK 승리 .. 백준 9657번 [돌 게임 3](C++) -yes6686- 티스토리 백준 문제 풀이: 9657 (돌 게임 3)문제 링크: https://www.acmicpc.net/problem/9657문제 설명:돌 게임 3은 상근이와 창영이가 번갈아가며 게임을 진행하는 게임입니다. 한 번의 턴에서 돌을 1개, 3개, 혹은 4개 가져갈 수 있습니다. 마지막 돌을 가져가는 사람이 승리하며, 시작하는 사람이 이길 수 있는지 확인합니다. - "SK"는 상근이가 승리, "CY"는 창영이가 승리입니다.문제 해결 코드#include using namespace std;int dp[1001]; // dp[i]: 돌이 i개 남았을 때 승리하는 사람 (1: SK, 2: CY)int main() { ios::sync_with_stdio(false); cin.tie(NULL); int n;.. 백준 1788번 [피보나치 수의 확장](C++) -yes6686- 티스토리 백준 문제 풀이: 1788 [피보나치 수의 확장]문제 링크: https://www.acmicpc.net/problem/1788문제 설명:피보나치 수열은 다음과 같은 점화식으로 정의됩니다:F(0) = 0, F(1) = 1F(n) = F(n-1) + F(n-2) (n ≥ 2)F(n) = F(n+2) - F(n+1) (n 이 문제에서는 정수 n에 대해 F(n)을 구하고, 다음을 출력해야 합니다:F(n)이 양수, 음수, 또는 0인지에 따라 각각 1, -1, 또는 0F(n)을 10억(1,000,000,000)으로 나눈 나머지문제 해결 코드#include #include #define MOD 1000000000using namespace std;int dp[1000001]; // F(n)을 저장하기 위한 배열int.. 백준 2293번 [동전 1](C++) -yes6686- 티스토리 백준 문제 풀이: 2293 [동전 1]문제 링크: https://www.acmicpc.net/problem/2293문제 설명:n가지 종류의 동전이 주어졌을 때, 주어진 동전들을 사용하여 가치의 합이 k원이 되는 경우의 수를 구하는 문제입니다.동전의 순서는 상관없으며, 각 동전은 무한정 사용할 수 있습니다.문제 해결 코드#include using namespace std;int coins[101]; // 동전의 가치를 저장하는 배열int dp[10001]; // 가치 합이 k원이 되는 경우의 수를 저장하는 배열int main() { ios::sync_with_stdio(false); cin.tie(NULL); int n, k; // n: 동전의 종류, k: 목표 금액 cin >>.. 백준 11057번 [오르막 수](C++) -yes6686- 티스토리 백준 문제 풀이: 11057 [오르막 수]문제 링크: https://www.acmicpc.net/problem/11057문제 설명:오르막 수는 자릿수의 숫자가 증가하는 형태를 가진 수입니다. 예를 들어, 2234나 111은 오르막 수입니다. 길이가 N인 오르막 수의 개수를 계산하는 문제입니다.다음 조건이 적용됩니다:N은 1 이상 1000 이하의 정수입니다.결과는 10007로 나눈 나머지를 출력합니다.문제 해결 코드#include #define MOD 10007using namespace std;int dp[1001][10]; // dp[length][digit]: 길이가 length이고 마지막 숫자가 digit인 오르막 수의 개수int main() { ios::sync_with_stdio(false.. 백준 1904번 [01타일](C++) -yes6686- 티스토리 백준 문제 풀이: 1904 [01타일]문제 링크: https://www.acmicpc.net/problem/1904문제 설명:길이가 N인 01 타일로 이루어진 모든 가능한 이진 문자열의 개수를 구하는 문제입니다. 타일은 1×2와 2×1의 블록으로 구성되며, 다음 규칙을 따릅니다:N개의 타일은 1과 0으로 이루어진 이진 문자열로 표현됩니다.길이가 1일 때는 "1", 길이가 2일 때는 "00" 또는 "11"입니다.결과는 15746으로 나눈 나머지를 출력합니다.문제 해결 코드#include using namespace std;int dp[1000001]; // dp[i]: 길이가 i인 01 타일의 경우의 수int main() { ios::sync_with_stdio(false); cin.tie(NU.. 백준 9465번 [스티커](C++) -yes6686- 티스토리 백준 문제 풀이: 9465 [스티커]문제 링크: https://www.acmicpc.net/problem/9465문제 설명:두 줄로 구성된 스티커에서 스티커를 선택해 최대 점수를 얻는 문제입니다. 다음 조건이 적용됩니다:한 열에서 두 개의 스티커 중 하나만 선택할 수 있습니다.인접한 열에서 선택한 스티커와 같은 행의 스티커를 선택할 수 없습니다.점수의 합이 최대가 되는 값을 출력합니다.문제 해결 코드#include #include using namespace std;int arr[3][100001]; // 스티커 점수를 저장하는 배열int dp[3][100001]; // 최대 점수를 저장하는 DP 배열int main() { ios::sync_with_stdio(false); cin.tie(N.. 백준 11052번 [카드 구매하기](C++) -yes6686- 티스토리 백준 문제 풀이: 11052 [카드 구매하기]문제 링크: https://www.acmicpc.net/problem/11052문제 설명:1부터 N까지의 카드 묶음을 살 수 있으며, 각 카드 묶음의 가격이 주어질 때, 정확히 N개의 카드를 구매하는 데 지불해야 하는 최대 비용을 구하는 문제입니다.즉, 카드 묶음을 어떻게 조합하느냐에 따라 최대 비용을 얻도록 해야 합니다.문제 해결 코드#include #include using namespace std;int arr[1001]; // 카드 묶음의 가격을 저장하는 배열int dp[1001]; // N개의 카드를 구매하는 데 지불해야 하는 최대 비용int main() { ios::sync_with_stdio(false); cin.tie(NULL); .. 이전 1 2 3 4 5 6 7 다음
