다이나믹 프로그래밍 검색 결과

해당 글 14건

[백준] C++ 알고리즘 2294번 - 동전2문제

문제 https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주 www.acmicpc.net 소스코드 #include #include #include #include #include using namespace std; int dp[10001]; int arr[101]; int main() { ios_base::sync_with_stdio(false), cin.tie(NULL); int n, k; cin >> n >> k; for (int i = 1; ..
Algorithm/dynamic programming 2021. 9. 10. 20:50

[백준] 알고리즘 3-5일차 다이나믹 프로그래밍

1. 15988번 : 1,2,3 더하기 3 15988번: 1, 2, 3 더하기 3 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 1,2,3 더하기와 같은 문제로 풀면된다. DP[N] = DP[N-1] + DP[N-2] + DP[N-3] 마지막 자리를 1로 할 것인지 2로 할 것인지 3으로 할 것인지를 결정해주면 된다. 매번 테스트케이스때마다 DP안에 있는 값을 계산해주면 너무 비효율적이다. 백만까지 모든 경우를 다구한 이후에 N값을 입력받아 그냥 출력해주면 된다. 문제에서 10억9로 나눈 나머지를 출력하라 했으니 분명 INT의 범위보다 높을 것이므로 LONG LONG으로 설정해준다. #include..
Algorithm/정리 2021. 8. 12. 12:42

[백준] 알고리즘 3-2일차 다이나믹 프로그래밍

연속, 인접이라는 처리는 마지막에 무엇이 오는지 기록하는 방식으로 문제를 해결한다. 1. 15990번 : 1,2,3 더하기 5 15990번: 1, 2, 3 더하기 5 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net DP[i][j] i를 1, 2, 3의 합으로 나타내는 방법의 수와 j가 마지막에 오는 경우의 조건을 추가한 점화식 이전에 풀었던 문제와 다른점은 조건이 하나 추가되었기 때문에 연속된 숫자의 경우를 배제해야한다. DP[i][1] i를 합으로 나타내는데 마지막에 1이 오는경우는 = DP[i-1][2] + DP[i-1][3] i-1까지의 마지막 숫자가 1만아니면 된다. 즉 마지막에 오는 숫자를 ..
Algorithm/정리 2021. 8. 7. 21:19

[백준] 알고리즘 3일차 다이나믹 프로그래밍

큰 문제를 작은 문제로 나눠서 푸는 알고리즘 1. 겹치는 작은 문제 ex) 피보나치 수 Fn = Fn-1 + Fn-2 - 큰 문제와 작은 문제를 같은 방법으로 풀 수 있다. - 문제를 작은 문제로 쪼갤 수 있다. 큰문제 = 작은 문제 2. 최적 부분 구조 - 문제의 정답을 작은 문제의 정답에서 구할 수 있다. - 문제의 크기에 상관없이 어떤 한 문제의 정답은 일정하다. 즉 다이나믹 프로그래밍은 두 가지를 만족한다. - 2를 만족하기에 같은 문제는 구할 때마다 정답이 같다. - 정답을 구했으면 배열에 저장한다. - 메모하는 부분을 메모제이션이라고 한다. - 모든 문제를 풀어야 한다. - 모든 문제는 1번만 풀어야 한다. 방법 문제를 푸는데 필요한 재귀식인 점화식을 구해야한다. 문제를 작게 만드는 방법을 찾..
Algorithm/정리 2021. 8. 7. 14:39

[백준] 알고리즘 15990번 - 1, 2, 3 더하기 5 문제

문제 - www.acmicpc.net/problem/15990 15990번: 1, 2, 3 더하기 5 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 소스코드 #include using namespace std; long long dp[3][100001]; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int T,mod=1000000009; cin >> T; dp[0][1] = 1, dp[1][2] = 1, dp[2][3] = 1, dp[0][3] = 1, dp[1][3] = 1, dp[2][3]; while..
Algorithm/dynamic programming 2021. 4. 5. 22:05

[백준] 알고리즘 9095번 - 1, 2, 3 더하기 문제

문제 : https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 소스코드 #include using namespace std; long long dp[1000001]; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int T,mod=1000000009; cin >> T; dp[1] = 1, dp[2] = 2, dp[3] = 4; while (T--) { int n; cin >> n; for (int i = 4; i
Algorithm/dynamic programming 2021. 4. 5. 17:03

[백준] 알고리즘 1965번 - 상자넣기 문제

문제 www.acmicpc.net/problem/1965 1965번: 상자넣기 정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 www.acmicpc.net 소스코드 #include using namespace std; int arr[1001]; int dp[1001]; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n,ans=0; cin >> n; for (int i = 0; i > arr[i]; for (int i = 0; i < n; i+..
Algorithm/dynamic programming 2021. 4. 3. 18:58

[백준] 알고리즘 14606번 - 피자 문제

문제 www.acmicpc.net/problem/14606 14606번: 피자 (Small) 예제1의 입력이 1이므로, 게임 시작부터 갑이 분리할 수 있는 피자탑이 없습니다. 따라서 갑이 얻는 즐거움은 0입니다. 예제2의 정답 3은 다음과 같은 과정을 통해 얻어집니다. 먼저 놀이를 시작 www.acmicpc.net 소스코드 #include using namespace std; int dp[11]; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n; cin >> n; dp[1] = 0, dp[2] = 1; for (int i = 3; i
Algorithm/dynamic programming 2021. 3. 27. 20:18

[백준] 알고리즘 13699번 - 점화식 문제

문제 www.acmicpc.net/problem/13699 13699번: 점화식 다음의 점화식에 의해 정의된 수열 t(n)을 생각하자: t(0)=1 t(n)=t(0)*t(n-1)+t(1)*t(n-2)+...+t(n-1)*t(0) 이 정의에 따르면, t(1)=t(0)*t(0)=1 t(2)=t(0)*t(1)+t(1)*t(0)=2 t(3)=t(0)*t(2)+t(1)*t(1)+t(2)*t(0)=5 ... 주어진 입력 0 ≤ n www.acmicpc.net 소스코드 #include using namespace std; long long dp[36]; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n; cin >> ..
Algorithm/dynamic programming 2021. 3. 26. 23:49