BAEKJOON/다이나믹 프로그래밍 (49) 썸네일형 리스트형 백준 1149번 [RGB거리](C++) -yes6686- 티스토리 백준 문제 풀이: 1149 [RGB거리]문제 링크: https://www.acmicpc.net/problem/1149문제 설명:RGB거리에는 집이 n개 있으며, 각 집은 빨강(R), 초록(G), 파랑(B) 중 하나의 색으로 칠해야 합니다. 또한, 인접한 두 집은 같은 색을 가질 수 없습니다. 각 집을 칠하는 비용이 주어졌을 때, 모든 집을 칠하는 데 드는 최소 비용을 구하는 프로그램을 작성하세요.입력:첫째 줄에 집의 수 n이 주어집니다. (2 ≤ n ≤ 1,000)둘째 줄부터 n개의 줄에는 빨강, 초록, 파랑으로 칠하는 비용이 주어집니다. (1 ≤ 비용 ≤ 1,000)출력:모든 집을 칠하는 데 드는 최소 비용을 출력합니다.예시:입력:326 40 8349 60 5713 89 99출력:96문제 해결 코드#i.. 백준 17626번 [Four Squares](C++) -yes6686- 티스토리 백준 문제 풀이: 17626 [Four Squares]문제 링크: https://www.acmicpc.net/problem/17626문제 설명:주어진 자연수 n을 네 개 이하의 제곱수의 합으로 표현할 때, 필요한 제곱수의 최소 개수를 구하는 문제입니다. 예를 들어, n = 7일 때, 4 + 1 + 1 + 1로 표현할 수 있으므로 답은 4입니다.입력:첫째 줄에 자연수 n이 주어집니다. (1 ≤ n ≤ 50,000)출력:n을 네 개 이하의 제곱수의 합으로 표현할 때 필요한 제곱수의 최소 개수를 출력합니다.예시:입력:7출력:4문제 해결 코드#include #include using namespace std;int dp[50001]; // dp[i]: i를 표현하는 데 필요한 최소 제곱수의 개수int main(.. 백준 11727번 [2×n 타일링 2](C++) -yes6686- 티스토리 백준 문제 풀이: 11727 [2×n 타일링 2]문제 링크: https://www.acmicpc.net/problem/11727문제 설명:2×n 크기의 직사각형을 1×2, 2×1, 2×2 크기의 타일로 채우는 방법의 수를 구하는 문제입니다. 방법의 수는 10,007로 나눈 나머지를 출력합니다.입력:첫째 줄에 n이 주어집니다. (1 ≤ n ≤ 1,000)출력:2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력합니다.예시:입력:2출력:3문제 해결 코드#include using namespace std;int dp[1001]; // dp[i]: 2×i 크기의 직사각형을 채우는 방법의 수int main() { int n; cin >> n; dp[1] = 1; // 2×.. 백준 8394번 [악수](C++) -yes6686- 티스토리 백준 문제 풀이: 8394번 [악수]문제 링크: https://www.acmicpc.net/problem/8394문제 설명:N명이 원탁에 앉아 서로 악수를 할 때, 마지막 사람이 악수를 하지 않더라도 나올 수 있는 악수의 총 경우의 수를 계산하는 문제입니다. 이 문제는 피보나치 수열의 점화식을 기반으로 풀 수 있습니다. 결과는 마지막 자리 숫자만 출력합니다.문제 해결 코드#include using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(NULL); int n; cin >> n; if (n == 1 || n == 2 || n == 3) { cout 코드 설명위 코드는 피보나치 점화식을 사용하여.. 백준 11726번 [2×n 타일링](C++) -yes6686- 티스토리 백준 문제 풀이: 11726 [2×n 타일링]문제 링크: https://www.acmicpc.net/problem/11726문제 설명:2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 문제입니다. 결과는 10,007로 나눈 나머지를 출력합니다.문제 해결 코드// 백준 11726 - 2×n 타일링#include using namespace std;int dp[1001]; // dp[i]: 2×i 크기의 직사각형을 채우는 방법의 수int main() { int n; cin >> n; // 초기 조건 dp[1] = 1; // 2×1 직사각형을 채우는 방법은 1가지 dp[2] = 2; // 2×2 직사각형을 채우는 방법은 2가지 // 동적 프로그래밍 .. 백준 18353번 [병사 배치하기](C++) -yes6686- 티스토리 백준 문제 풀이: 18353 [병사 배치하기]문제 링크: https://www.acmicpc.net/problem/18353문제 설명:n명의 병사가 전투력을 기준으로 주어졌을 때, 내림차순으로 배치하기 위해 제외해야 할 최소 병사 수를 구하는 문제입니다.병사의 전투력 배열에서 내림차순 부분 수열의 길이를 최대로 만들고, 전체 병사 수에서 이를 빼면 제외해야 하는 병사 수가 됩니다.문제 해결 코드#include using namespace std;int arr[2001]; // 병사의 전투력 배열int dp[2001]; // DP 배열int main() { ios::sync_with_stdio(false); cin.tie(NULL); int n; cin >> n; // 병사의 수 입.. 백준 25421번 [조건에 맞는 정수의 개수](C++) -yes6686- 티스토리 백준 문제 풀이: 25421 (조건에 맞는 정수의 개수)문제 링크: https://www.acmicpc.net/problem/25421문제 설명:주어진 조건에 따라 길이 n의 정수를 만들 수 있는 경우의 수를 구합니다. 각 자리의 숫자는 **1~9**까지이며, 인접한 자리의 숫자 차이가 최대 **2 이하**여야 합니다. 결과를 **987654321**로 나눈 나머지를 출력합니다.문제 해결 코드#include #define MOD 987654321using namespace std;long long int arr[10]; // 현재 자리에서 가능한 숫자 개수long long int carr[10]; // 이전 자리 숫자 개수를 복사할 배열int main() { ios::sync_with_stdio(.. 백준 1699번 [제곱수의 합](C++) -yes6686- 티스토리 백준 문제 풀이: 1699 (제곱수의 합)문제 링크: https://www.acmicpc.net/problem/1699문제 설명:주어진 자연수 n을 제곱수의 합으로 나타낼 때, 필요한 제곱수 항의 최소 개수를 구하는 문제입니다. 예를 들어 n = 7이면 4 + 1 + 1 + 1 = 7로 최소 4개의 항이 필요합니다.문제 해결 코드#include #include using namespace std;int dp[100001];int main() { ios::sync_with_stdio(false); cin.tie(NULL); int n; cin >> n; dp[1] = 1; // 1은 자기 자신이 제곱수이므로 1개 // DP 배열 초기화 for (int i = 2; i .. 이전 1 2 3 4 5 ··· 7 다음
