본문 바로가기

Beakjoon/dynamic programming

 (9)
[백준] 1932번 정수 삼각형 (C++) - dynamic programming 문제 https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 코드 #include using namespace std; int dp[500][500]; int main(){ int n; cin >> n; for(int i=0; i dp[i][j]; } } for(int i=1; i
[백준] 11659번 구간 합 구하기 4 (C++) - dynamic programming 문제 https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 코드 #include using namespace std; int dp[100001]; int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n, m; cin >> n >> m; for(int i=1; i> a; dp[i] += dp[i-1]+a; } for(int k=0; k>..
[백준] 14501번 퇴사 (C++) - dynamic programming 문제 https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 코드 #include using namespace std; int dp[16]; int t[16]; int p[16]; int main(){ int n; cin >> n; for(int i=1; i> t[i] >> p[i]; } for(int i=n; i>=1; i--){ if(t[i]+i-1 > n){ dp[i] = dp[i+1]; }else{ dp[i] = max(dp[i+1], dp[i+t[i]]+p[i]); } } cout 20) 1일 - 잡혀있는 상담기간이 3일이므로 1~3일에 걸쳐 상담을 진행할 수 있다. → 지금까지..
[백준] 1699번 제곱수의 합 (C++) - dynamic programming 문제 https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net 코드 #include using namespace std; int dp[100001] = {0}; int main(){ int n; cin >> n; for(int i=1; i
[백준] 1912번 연속합 (C++) - dynamic programming 문제 https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 코드 #include using namespace std; int dp[100001] = {-1001,}; int main(){ int n; cin >> n; int result = -1001; for(int i=1; i> a; if(i == 1 || a > a+dp[i-1]){ dp[i] = a; } else{ dp[i] = a+dp[i-1]; } if(dp[i] > result){ result = ..
[백준] 15990번 1, 2, 3 더하기 5 (C++) - dynamic programming 문제 https://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[100001][3] = {{0,0,0},{1,0,0},{0,1,0},{1,1,1}}; long long sum[100001] = {0,1,1,3}; int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int t; cin >> t; for(int i=0; i> n; if(dp[n..
[백준] 11052번 카드 구매하기 (C++) - dynamic programming 문제 https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 코드 #include using namespace std; int main(){ int n; int dp[10001] = {0,}; cin >> n; for(int i=1; i> a; int max = a; for(int j=1; j
[백준] 1463번 1로 만들기 (C++) - dynamic programming 문제 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 코드 #include using namespace std; int arr[1000001]; int main(){ int n; cin >> n; arr[2] = 1; arr[3] = 1; for(int i=4; i

티스토리툴바