728x90 🥇Baekjoon Solutions/동적계획법4 [C++] 백준 14852번: 타일 채우기 3 https://www.acmicpc.net/problem/14852 14852번: 타일 채우기 3 첫째 줄에 경우의 수를 1,000,000,007로 나눈 나머지를 출력한다. www.acmicpc.net 중요풀이 다이나믹 프로그래밍을 사용하여 반복되는 행동을 for문 또는 재귀를 통해서 풀이를 진행합니다. dp[i]는 3*dp[i-2](1*2 두개, 1*1 두개 + 1*2한개 경우 2개 따라서 3가지) + 2*dp[i-1](1*1 두개, 2*1한개) 점화식은 dp[i] = 3 * dp[i - 2] + 2 * dp[i - 1] + (2 * dp[i-3] + ... + 2 * dp[0])이 나옵니다. 소스코드 #include using namespace std; int dp[1000001]; long long.. 2021. 8. 28. [C++] 백준 11659번: 구간 합 구하기 4 https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 최초풀이 DP알고리즘을 활용하여 풀이를 진행하였고 빠른 출력 처리를 해주어야 합니다. #include using namespace std; int dp[100001]; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int N, M, k; cin >> N >> M; for (int i.. 2021. 8. 1. [C++] 백준 11660번: 구간 합 구하기 5 https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 최초풀이 시간초과 에러가 많이 발생하는 문제입니다. DP 알고리즘을 잘활용하고 빠른 입출력 처리도 해주어야 합니다. #include using namespace std; int dp[1025][1025]; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int N,.. 2021. 8. 1. [C++] 백준 1932번: 정수 삼각형 https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 최초풀이 위에서부터 아래로 규칙에 따라 최대 값을 갱신해가는 배열을 만듭니다. 가장 아래 단계까지 구했다면 그 단계의 최대 값을 출력해 줍니다. #include using namespace std; int dp[501][501]; int main() { int n, temp; cin >> n; for (int i = 1; i > temp; if (j == 0) dp[i][j] = temp + dp[i - 1][j]; else if (j == i - 1) dp[i][j].. 2021. 8. 1. 이전 1 다음 728x90
