- 피보나치 함수
0과1의 호출수는 배열을 통해 증가하는것을 확인할수있다 0일경우를 예외로 두고 0,1,1 .... 일때
p[i] = p[i - 1] + p [i - 2] 이므로 반복문을 통해 문제에서 요구하는 40까지의 값을 미리 계산한뒤 입력받은 값의 0과 1 반복수를 출력해주면 된다.
- 신나는 함수 실행
모든수를 재귀를 통해 계산하면 실행시간 조건을 만족할수없다 그러므로 DP를 통해 값을 저장하면서 문제를 해결하면 메모리를 많이 사용하지만 실행시간을 단축할수있다.
주어진 조건 2개안이라면 리턴값을 해주고 아니라면 캐시를 불러온다 캐시의 값이있다면 캐시의 값을 리턴해주고
아니라면 그때의 값을 계산해주고 캐시의 해당값을 기록해준다.
int w(int a, int b, int c)
{
if (a <= 0 || b <= 0 || c <= 0)
return 1;
if (a > 20 || b > 20 || c > 20)
return w(20, 20, 20);
int &result = cache[a][b][c];
if (result != 0)
return cache[a][b][c];
if (a < b && b < c)
return result = w(a, b, c - 1) + w(a, b - 1, c - 1) - w(a, b - 1, c);
else
return result = w(a - 1, b, c) + w(a - 1, b - 1, c) + w(a - 1, b, c - 1) - w(a - 1, b - 1, c - 1);
}3.01타일
문제를 진행해보면 해당 수열은 피보나치 수열로 증가하는것을 확인할수있다 하지만 더쉬운방법은 i일때의 방법은 i-2의 방법에 0을 뒤에 붙이는것과 i-1의 방법에 앞에 1을 붙이는경우의 수라는것을 파악하는것이다 이는 중복값이 없는 배열을 구할수있는 방법이다.
int main()
{
int n,i;
int d[1000001];
cin >> n;
d[0] = 0;
d[1] = 1;
d[2] = 2;
for (i = 3; i <= n; i++)
{
d[i] = d[i - 1] + d[i - 2];
d[i] %= 15746;
}
cout << d[n] << endl;
}4.파도반 수열
long long 배열(크기 100 long long인 이유는 int 형의 범위를 초과해서) 을 선언한후 처음 5개의 값을 초기화해준다 다음 i번쨰 값은 i-1값 + i-5값이다.
5.RGB거리
arr배열의 각 집을 칠할때 필요한 값을 입력받는다 dp 배열에는 arr의 처음값을 넣어준다
dp배열 3개는 각각 처음을 r,g,b값으로 칠했을 경우이며 각각 앞으로 진행하며 전단계의 자신과 다른 dp의값 + 자기 자리의 arr값을 더해준다 그렇다면 dp각 배열 3개에는 각 경우의 최소값을 가지고있을것이고 이를 비교후 최소값을 출력해준면된다
- 정수 삼각형
값을 입력받아 arr배열에 저장한후 dp를 이용해 해결한다 한줄에 처음값과 마지막값은 각각 0과 전 줄의 마지막값을 받는것이고 그사이는 대각선위의 두값중 큰값을 가져오는식으로 피라미드를 만든다 마지막줄에 값들을 비교해 가장 큰값을 출력하면 된다.
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int cnt, res;
int arr[100][100] = { 0, };
int dp[100][100] = { 0, };
cin >> cnt;
for (int i = 0; i < cnt; i++)
{
for (int j = 0; j <= i; j++)
{
cin >> arr[i][j];
}
}
dp[0][0] = arr[0][0];
for (int i = 1; i < cnt; i++)
{
for (int j = 0; j <= i; j++)
{
if (j == 0)
dp[i][j] = dp[i - 1][j] + arr[i][j];
else if (j == i)
dp[i][j] = dp[i - 1][i-1] + arr[i][j];
else
dp[i][j] = max(dp[i - 1][j-1],dp[i- 1][j]) + arr[i][j];
}
}
res = dp[cnt-1][0];
for (int j = 0; j < cnt; j++)
{
if (dp[cnt-1][j] >= res)
res = dp[cnt-1][j];
}
cout << res << endl;
}7.계단오르기
마지막계단의 최대값은 마지막 전전 계단까지의 최대값 + 마지막계단값 과 마지막계단값 + 전계단의 값 + 전전전계단까지의 최대값을 비교하면된다
dp 0 1 2까지는 기본값을 설정해주고 이후는 반복문을 통해 최대값을 계산해나가면 된다.
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int cnt;
int arr[300];
int dp[300];
cin >> cnt;
for (int i = 0; i < cnt; i++)
{
cin >> arr[i];
}
dp[0] = arr[0];
dp[1] = max(arr[0] + arr[1], arr[0]);
dp[2] = max(arr[0] + arr[2], arr[1] + arr[2]);
for (int i = 3; i < cnt; i++)
{
dp[i] = max(dp[i - 2] + arr[i], dp[i - 3] + arr[i] + arr[i - 1]);
}
cout << dp[cnt - 1] << endl;
}
- 1로 만들기
dp[i] 는 i일때 1로 만드는데 걸리는 횟수를 의미한다 2와 3 에 각각 기본값 1일 넣어준후 시작한다 경우는 4가지이다 i가 6으로 나눠 떨어지는경우 3으로 나눠 떨어지는경우 2로나눠 떨어지는경우 그외의 경우 각각 3,2,2,1하나의 방법이 있고 이 방법의 최솟값을 넣어주면 원하는 값까지 배열을 만들어 나가면된다.
#include <iostream>
#include <algorithm>
#define MOD 1000000000
using namespace std;
int main()
{
int cnt,sum = 0;
int dp[100][10];
cin >> cnt;
dp[0][0] = 0;
for (int i = 1; i < 10; i++)
{
dp[0][i] = 1;
}
for (int i = 1; i < cnt; i++)
{
for (int j = 0; j < 10; j++)
{
if (j == 0)
dp[i][j] = dp[i - 1][1] % MOD;
else if (j == 9)
dp[i][j] = dp[i - 1][8] % MOD;
else
dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % MOD;
}
}
for (int i = 0; i < 10; i++)
{
sum += dp[cnt - 1][i];
sum %= MOD;
}
cout << sum % MOD << endl;
}9.쉬운 계단수
자릿수0 1 2 3 4 5 6 7 8 9
한자리0 1 1 1 1 1 1 1 1 1
두자리1 1 2 2 2 2 2 2 2 2
....
이런식으로 0과 9일때는 1과 8을 그대로 가져오고 아닐경우엔 i-1 과 i + 1을 더해주면된다
오버플로가 발생하기 쉬우므로 덧셈후엔 mod연산을 해준다
#include <iostream>
#include <algorithm>
#define MOD 1000000000
using namespace std;
int main()
{
int cnt,sum = 0;
int dp[100][10];
cin >> cnt;
dp[0][0] = 0;
for (int i = 1; i < 10; i++)
{
dp[0][i] = 1;
}
for (int i = 1; i < cnt; i++)
{
for (int j = 0; j < 10; j++)
{
if (j == 0)
dp[i][j] = dp[i - 1][1] % MOD;
else if (j == 9)
dp[i][j] = dp[i - 1][8] % MOD;
else
dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % MOD;
}
}
for (int i = 0; i < 10; i++)
{
sum += dp[cnt - 1][i];
sum %= MOD;
}
cout << sum % MOD << endl;
}
- 포도주 시식
포도주를 먹는규칙인
dp[i] = max(arr[i] + arr[i - 1] + dp[i - 3], dp[i - 2] + arr[i]);
는 맞춰서 맞는줄알았는데 문제가 계속 틀려서 인터넷을 참고하니 2번연속 안마시는경우를 고려해야한다 이때 dp[i]값을 최대값으로 바꿔야한다.
dp[i] = max(dp[i], dp[i - 1]);
- 가장 긴 증가하는 부분수열
크기 1001의 배열 dp와 arr을 만들고 arr은 수열의 값으로 dp는 1로 초기화한다(각 배열의 인자는 최소 1의 수열을 만들수있음으로)
그후 반복문을 통해 자기보다 전의 자기보다 작은 값의 dp값+1 과 자신의 dp값중 큰값을 자신의 dp값으로 한다 i가 증가할때마다 res에 dp[i]의 최대값을 자신과 비교해서 넣으면 된다
#include <iostream>
#include <algorithm>
using namespace std;
int main(void)
{
int dp[1001];
int arr[1001];
int n,res = 1;
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> arr[i];
dp[i] = 1;
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < i; j++)
{
if (arr[i] > arr[j])
{
dp[i] = max(dp[i],dp[j] + 1);
}
}
res = max(res,dp[i]);
}
cout << res << endl;
}
- 가장 킨 바이토닉 부분 수열
이 문제의 핵심 왼쪽에서 증가하는 순으로 dp를 구하고 오른쪽에서 왼쪽으로 증가하는순으로 rev_dp를 구한후 두 배열을 더해준후 1을빼면된다 (자기자신이 2번 들어감으로) 동시에 res도 최대값으로 결정해주면 문제를 해결할수있다.
#include <iostream>
#include <algorithm>
using namespace std;
int main(void)
{
int dp[1001];
int rev_dp[1001];
int arr[1001];
int n, res = 1;
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> arr[i];
dp[i] = 1;
rev_dp[i] = 1;
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < i; j++)
{
if (arr[i] > arr[j])
{
dp[i] = max(dp[i], dp[j] + 1);
}
}
}
for (int i = n-1; i >= 0; i--)
{
for (int j = n-1; j > i; j--)
{
if (arr[i] > arr[j])
{
rev_dp[i] = max(rev_dp[i], rev_dp[j] + 1);
}
}
}
for (int i = 0; i < n; i++)
{
dp[i] = dp[i] + rev_dp[i] - 1;
res = max(res, dp[i]);
}
cout << res << endl;
}13.전깃줄
여러번 시도 했으나 문제가 해결되지 않아 인터넷을 참고했다 dp를 활용하되 벡터를 이용해 순서대로 정렬하고 가장큰 전깃줄 제거수를 구한후 전체값에서 빼는것이 해답이였다.
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int dp[102];
int main() {
int n, a, b;
int result = 0;
cin >> n;
vector<pair<int, int>> v;
v.emplace_back(0, 0);
for (int i = 0; i < n; i++)
{
cin >> a >> b;
v.emplace_back(a, b);
}
sort(v.begin(), v.end());
for (int i = 1; i <= n; i++)
{
for (int j = 0; j < i; j++)
{
if (v[i].second > v[j].second)
{
if (dp[j] >= dp[i])
{
dp[i] = dp[j] + 1;
}
}
}
result = max(result, dp[i]);
}
cout << n - result << endl;
return 0;
}14.lcs
2차원배열을 만들고 각 문자열을 s1 s2로 받고 s1을 하나씩증가시키고 s2도 그후 하나씩 증가시키면서 겹치는 문자열을 비교하며 나아간다 dp 배열의 마지막값에서 최대 문자열의 길이를 파악할수있다.
#include<cstdio>
#include<algorithm>
using namespace std;
char s1[1002], s2[1002];
int dp[1001][1001], i, j;
int main() {
scanf("%s %s", s1 + 1, s2 + 1);
for (i = 1; s1[i]; i++)
for (j = 1; s2[j]; j++)
dp[i][j] = max({ dp[i][j - 1], dp[i - 1][j],
dp[i - 1][j - 1] + (s1[i] == s2[j])
});
printf("%d", dp[i - 1][j - 1]);
return 0;
}15.연속합
dp를 통해 해결하며 연속된값이기때문에 dp값은 계속해서 더하는것이 아닌 전 dp에 자신을 더한값이 자기자신값보다 작다면 dp를 자기자신으로 초기화 시킨다이다 굳이 뒷값을 계속해서 가져갈필요가없다.
#include <iostream>
#include <algorithm>
using namespace std;
int main(void)
{
int n, ans;
int arr[100000];
int dp[10000];
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> arr[i];
}
dp[0] = arr[0];
ans = dp[0];
for (int i = 1; i < n; i++)
{
dp[i] = max(dp[i - 1] + arr[i],arr[i]);
ans = max(dp[i], ans);
}
cout << ans << endl;
}.16 평범한배낭
문제가 잘 이해되지않아 인터넷의 답을 참고했다 이번 dp 문제중 가장 난이도가 높았던거 같다 아이템의갯수 * 배낭의 최대 무게의 배열을 만들고 아이템을 넣을지 안넣을지 비교하고 넣는다면 그값이 충분히 큰지 비교해나가면서 dp의 최대값을 구하는 것이 관건이었다.
#include <iostream>
#include <algorithm>
using namespace std;
int main(void)
{
int n, ans;
int arr[100000];
int dp[10000];
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> arr[i];
}
dp[0] = arr[0];
ans = dp[0];
for (int i = 1; i < n; i++)
{
dp[i] = max(dp[i - 1] + arr[i],arr[i]);
ans = max(dp[i], ans);
}
cout << ans << endl;
}