[코딩테스트][Dynamic Programming] 백준 9465, 2156, 11053, 11055, 11722, 11054, 1912, 2579
백준 9465, 2156, 11053, 11055, 11722, 11054, 1912, 2579
https://github.com/h-dyeon/Algorithm
백준 9465 Stickers
136ms … dp[i] [j] 는 i행, j열의 스티커까지 선택했을때의 최대값을 의미한다.
#include <iostream>
#include <algorithm>
using namespace std;
int dp[2][100002];
int arr[2][100002];
int main() {
int T, n;
scanf_s("%d", &T);
while (T--) {
scanf_s("%d", &n);
//입력
for (int k = 0; k < 2; k++) {
int t;
for (int i = 1; i <= n; i++) {
scanf_s("%d", &t);
arr[k][i] = t;
}
}
dp[0][1] = arr[0][1];
dp[1][1] = arr[1][1];
//풀이
for (int i = 2; i <= n; i++) {
dp[0][i] = max(dp[1][i - 1] , dp[1][i - 2]) + arr[0][i];
dp[1][i] = max(dp[0][i - 1] , dp[0][i - 2]) + arr[1][i];
}
//출력
int s = max(dp[0][n], dp[1][n]);
printf("%d\n", s);
//cout << max(dp[0][n], dp[1][n]) << "\n";
}
return 0;
}
백준 2156 : 포도주 시식
출력과 입력에서 서식문자 외우기
#include <iostream>
#include <algorithm>
using namespace std;
long long arr[10001];
long long dp[3][10001];
// . . X : 0
// . X O : 1
// X O O : 2
int main() {
int n;
scanf_s("%d", &n);
for (int i = 1; i <= n; i++) {
scanf_s("%lld", &arr[i]);
}
dp[0][1] = 0;
dp[1][1] = arr[1];
dp[2][1] = arr[1];
for (int i = 2; i <= n; i++) {
dp[0][i] = max(dp[0][i - 1] , dp[1][i - 1]);
dp[0][i] = max(dp[0][i] , dp[2][i - 1] );
dp[1][i] = dp[0][i - 1] + arr[i];
dp[2][i] = dp[1][i - 1] + arr[i];
}
long long s = max(dp[0][n], dp[1][n]);
s=max(s, dp[2][n]);
printf("%lli",s);
return 0;
}
//https://www.acmicpc.net/source/3760615
//저장할 필요가 없는 값은 버릴것
#include<cstdio>
#include<algorithm>
using namespace std;
int dp[3], tmp;
int main()
{
int n, x;
scanf("%d", &n);
while (n--)
{
scanf("%d", &x);
tmp = max(dp[0], max(dp[1], dp[2]));
if (dp[1]) dp[2] = dp[1] + x;
dp[1] = dp[0] + x;
dp[0] = tmp;
}
printf("%d\n", max(dp[0], max(dp[1], dp[2])));
}
백준 11053 : 가장 긴 증가하는 부분 수열
dp를 1로 초기화를 해야하는데 이를 빠뜨려서 한참 헤맸다. 수열의 길이가 아무리 짧아도 무조건 1인데 이를 0으로 착각했다. 그리고 dp로 아무리 생각해봐도 이중for문말고는 답이 없는데 다른방법은 없으려나
#include <iostream>
#include <algorithm>
using namespace std;
int arr[10001];
int dp[10001];
int main() {
int n, answer=0;
scanf_s("%d", &n);
for (int i = 1; i <= n; i++) {
scanf_s("%d", &arr[i]);
dp[i] = 1;
for (int j = 1; j < n; j++) {
if (arr[i] > arr[j])
dp[i] =max(dp[i], dp[j] + 1);
}
answer = answer < dp[i] ? dp[i] : answer;
}
printf("%d", answer);
return 0;
}
백준 11055 : 가장 큰 증가 부분 수열
#include <iostream>
#include <algorithm>
using namespace std;
int arr[1001];
int dp[1001];
int main() {
int n, Max=0;
scanf_s("%d", &n);
for (int i = 1; i <= n; i++) {
scanf_s("%d", &arr[i]);
//풀이
dp[i] = arr[i];
for (int j = 1; j < n; j++) {
if (arr[i] > arr[j])
dp[i] =max(dp[i], dp[j] + arr[i]);
}
Max = Max < dp[i] ? dp[i] : Max;
}
printf("%d", Max);
return 0;
}
백준 11722 : 가장 긴 감소하는 부분 순열
#include <iostream>
#include <algorithm>
using namespace std;
int arr[1001];
int dp[1001];
int main() {
int n, Max=0;
scanf_s("%d", &n);
for (int i = 1; i <= n; i++) {
scanf_s("%d", &arr[i]);
//풀이
dp[i] = 1;
for (int j = 1; j < n; j++) {
if (arr[i] < arr[j])
dp[i] =max(dp[i], dp[j] +1);
}
Max = Max < dp[i] ? dp[i] : Max;
}
printf("%d", Max);
return 0;
}
백준 11054 : 가장 긴 바이토닉 부분 수열
앞에서부터 오름차순 수열과 뒤에서부터 내림차순 수열을 각각 구해서 더했다. 그런데 4ms 의 성능이 나왔고 아래 코드는 0ms가 나왔다. algorithm의 max대신에 if문으로 바꿨는데도 내 코드는 그대로 4ms가 나온다. 뭐가 다른걸까
#include <iostream>
#include <algorithm>
using namespace std;
int arr[1001];
int dpUp[1001];
int dpDown[1001];
int main() {
int n;
scanf_s("%d", &n);
for (int i = 1; i <= n; i++) {
scanf_s("%d", &arr[i]);
//앞에서 부터 오름차순 수열 0123
dpUp[i] = 1;
for (int j = 1; j < i; j++) {
if (arr[i] > arr[j])
dpUp[i] = max(dpUp[i], dpUp[j] + 1);
}
}
//뒤에서부터 내림차순 수열 321
for (int i = n; i > 0; i--) {
dpDown[i] = 1;
for (int j = n; j > i; j--) {
if (arr[i] > arr[j])
dpDown[i] = max(dpDown[i], dpDown[j] + 1);
}
}
int Max = 0;
for (int i = 1; i <= n; i++) {
Max = max(Max, dpUp[i] + dpDown[i]-1);
}
printf("%d", Max);
return 0;
}
//https://www.acmicpc.net/source/16327047
#include <stdio.h>
int main(void) {
int N;
int Dp[2][1007] = {};
int A[1010] = {};
int max = 0;
scanf("%d", &N);
for (int i = 1; i <= N; i++)
scanf("%d", &A[i]);
for (int i = 1; i <= N; i++)
{
int maxA = 0;
for (int j = 0; j < i; j++) {
if (A[i] > A[j]) {
if (maxA < Dp[0][j])
maxA = Dp[0][j];
}
}
Dp[0][i] = maxA + 1;
}
for (int i = N; i >= 1; i--)
{
int maxA = 0;
for (int j = N; j > i; j--) {
if (A[i] > A[j]) {
if (maxA < Dp[1][j])
maxA = Dp[1][j];
}
}
if (Dp[1][i] < maxA + 1)
Dp[1][i] = maxA + 1;
}
for (int i = 1; i <= N; i++) {
if (max < Dp[0][i] + Dp[1][i])
max = Dp[0][i] + Dp[1][i];
}
printf("%d\n", max - 1);
}
백준 1912 : 연속합
#include <iostream>
#include <algorithm>
using namespace std;
long long arr[100001];
long long dp[100001];
int main() {
int n;
scanf_s("%lld", &n);
for (int i = 1; i <= n; i++) scanf_s("%lld", &arr[i]);
long long Max = -100000009;
for (int i = 1; i <= n; i++) {
dp[i] = max(arr[i], dp[i-1]+arr[i]);
Max = max(dp[i], Max);
}
printf("%lli",Max );
return 0;
}
백준 2579 : 계단 오르기
#include <iostream>
#include <algorithm>
using namespace std;
long long arr[301];
long long dp[301];
int main() {
int n;
scanf_s("%lld", &n);
for (int i = 1; i <= n; i++) scanf_s("%lld", &arr[i]);
dp[1] = arr[1];
dp[2] = max(arr[2], arr[1]+arr[2]);
dp[3]= max(arr[1] + arr[3], arr[2] + arr[3]);
for (int i = 4; i <= n; i++) {
dp[i] = max(dp[i-2]+arr[i] , dp[i-3]+arr[i-1]+arr[i]);
}
printf("%lli",dp[n] );
return 0;
}
