문자열을 끝냈고, BruteForce나 DP를 배우려고 했다.
하지만 BruteForce는 구현 카테고리의 문제를 풀 때 같이 하도록 하고,
DP를 배운다.
내용을 요약해보면,
DP라는 것은
이전의 값들로 다음의 값을 구하는 방식이라고 볼 수 있다.
보통 문제의 규칙인 점화식과, 시작값만 알아낸다면 사용할 수 있다.
구현하는 법은 미리 값을 담을 DP테이블을 생성하고,
시작값부터 점화식에따라 다음 값들을 계산하는 것이다.DP도 문자열처럼 특정 유형의 문제에 한정되지 않고,
천차만별의 난이도로 출제될 수가 있다.따라서 DP도 무조건 많은 유형의 문제를 풀어보는 것이 필요하다.
이게 DP문제일까 구별하는 방법은
N의 개수에 따라서 이전의 값이 다음의 값과 연관이 있는
점화식으로 표현이 될 수 있을까?를 찾을 수 있는가이다.
추가로 DP문제는 BFS로 구현할 수 있는게 생각보다 많다.
하지만 BFS는 DP보다 효율적이지 못하다.
1. 1463 - DP
https://www.acmicpc.net/problem/1463
DP의 가장 난이도가 쉬운 문제이다.
해결
#include <iostream>
using namespace std;
int REC(int N);
int dp[1000000+1] = {0,};
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int N;
cin >> N;
// 초기값
dp[1] = 0;
cout << REC(N);
return 0;
}
int REC(int N)
{
int t = 1000000;
int b = 1000000;
int o = 1000000;
if(N==1 || N==0)
{
return 0;
}
// N에 값이 없다면 부여
if(dp[N]==0)
{
if(N%3==0)
{
t = REC(N/3) + 1;
}
if(N%2==0)
{
b = REC(N/2) + 1;
}
o = REC(N-1) + 1;
dp[N] = min(min(t,o), min(b,o));
}
// N값을 리턴
return dp[N];
}풀이
목표값부터 역으로 계산한다.
해당 역연산을 한 수의 인덱스에 값이 없다면
또 역으로 계산한다.
이를 반복해서 초기값인 N == 1에 도착하면,
정의되어있는 값 0부터 순서대로 차례차례 계산된다.
점화식이 첫문단이고 초기값이 두번째 문단인 것이다.
DP를 담는 자료구조는 배열로 정했다.
이러면 DP문제는 사실상 끝
위의 문제를 BFS로 풀 수도 있다고 한다.
N부터 큐에 /3연산 인덱스, /2연산인덱스, -1인덱스를 넣어서
최단거리로 목표인 1에 도착한 것이 값일 것이다.
하지만 DP보다 비효율적이다. 그 이유는,
같은 연산을 여러번하기 때문이다.
12라면 4의 인덱스 3의인덱스 11의 인덱스에 갈 수 있다.
4에서는 또 3의 인덱스에 갈 수 있고, 11에서부터 또 3의 인덱스에 갈 수도 있다.
이런 중복계산을 막기위해, 중간에 값을 저장해두는 것이다.
그게 DP
2. 9095 - DP
https://www.acmicpc.net/problem/9095
해결
#include <iostream>
using namespace std;
int dp[12] = {0,};
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
dp[1] = 1;
dp[2] = 2;
dp[3] = 4;
int N, T;
for(int i=4;i<=11;i++)
{
dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
}
cin >> T;
while(T--)
{
cin >> N;
cout << dp[N];
cout << "\n";
}
return 0;
}
풀이
점화식은 dp[i] = dp[i-1] + dp[i-2] + dp[i-3]; 이다
[4일경우]
// 3일경우 +1
1+1+1+1
1+2+1
2+1+1
3+1
// 2일경우 +2
1+1+2
2+2
// 1일경우 +3
1+3- +1이나 +2나 +3만 할 수 있기 때문에,
N-1 N-2 N-3인 경우를 구하기만 하면 된다. - 초기값으로 N 1~3까지를 적어두었다.
- 그리고 dp배열을 채운다.
dp테이블을 다 채워두고
테스트 케이스마다 특정 N의 dp값을 꺼내서 쓴다.
- 뭐든간에 dp를 다 채우고 써야하기 떄문에
- N의 최대값이 11로 작기 때문에
dp테이블을 먼저 for문으로 다 채우고 진행한다.
3. 2579 - DP
https://www.acmicpc.net/problem/2579
해결
#include <iostream>
using namespace std;
int dp[301][301];
int stair[301];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
fill(&dp[0][0], &dp[300][300], 0);
int N;
cin >> N;
// 계단 value 입력
for(int i=1;i<=N;i++)
{
cin >> stair[i];
}
dp[1][1] = stair[1];
dp[1][2] = stair[1];
dp[2][1] = stair[2];
dp[2][2] = stair[1] + stair[2];
for(int i=3;i<=N;i++)
{
dp[i][1] = max(dp[i-2][1]+stair[i], dp[i-2][2]+stair[i]);
dp[i][2] = dp[i-1][1] + stair[i];
}
cout << max(dp[N][1], dp[N][2]);
return 0;
}풀이
어려웠다.
아이디어를 생각해내려면 많은 문제를 풀어봐야만
자연스레 튀어나오기 떄문이다.
dp를 담을 구조를 2차원 배열로 선언했다.
그 이유는, 연속해서 밟았는지를 확인하기 위한 배열을 추가했기 때문이다.
i의 1은 i로 가기위해서 연속된 계단을 밟지 않았다는 뜻이고,
i-1을 밟지 않았다는 말이다.
따라서 i-2를 무조건 밟았을 것이고,
i-2는 1번 밟았을지, 연속된 계단을 밟았을지 중에 max인 것을 더한다.
i의 2는 i를 가기 위해서 i-1을 무조건 밟았을 것이다.
그렇게 마지막 계단의 1과 2중에 큰 값을 출력하면 된다.
초기값은 위처럼 1과 2만 주었다.
4. 1149 - DP
https://www.acmicpc.net/problem/1149
해결
#include <iostream>
using namespace std;
int dp[1001][3];
int cost[1001][3];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int N;
cin >> N;
for(int i=1;i<=N;i++)
{
for(int j=0;j<3;j++)
{
cin >> cost[i][j];
}
}
dp[1][0] = cost[1][0];
dp[1][1] = cost[1][1];
dp[1][2] = cost[1][2];
for(int i=2;i<=N;i++)
{
dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + cost[i][0];
dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + cost[i][1];
dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + cost[i][2];
}
int c = min(dp[N][0], dp[N][1]);
c = min(c, dp[N][2]);
cout << c;
return 0;
}풀이
점화식을 보면 알 수 있다.
그냥 이전의 색과 다른 색을 더해준다.
그렇게 N까지 채우고,
N의 비용이 가장 적은 dp를 구하고 출력한다.
슬슬 문제를 푸는 감이 생긴다.
5. 11726 - DP
https://www.acmicpc.net/problem/11726
해결
#include <iostream>
using namespace std;
int dp[1001] = {0, };
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int N;
cin >> N;
dp[1] = 1;
dp[2] = 2;
for(int i=3; i<=N; i++)
{
dp[i] = (dp[i-1] + dp[i-2]) % 10007;
}
cout << dp[N];
return 0;
}풀이
그냥 구하면 되는 문제.
맨 앞줄을 세로 하나를 채우는 것으로 생각하면,
나머지 N-1인칸의 문제와 같고
맨 앞줄 2개를 가로 2개로 채우는 것으로 생각하면,
나머지 N-2인칸의 문제와 같으므로
위의 점화식을 이용하여 구한다.
문제에 핵심인 부분은 dp[i] = (dp[i-1] + dp[i-2]) % 10007;인데,
최종 값에 10007을 나누면 오류가 난다.
그 이유는 1000의 최종값이 위와 같기 때문이다.
int형으로 표현할 수가 없는 값이다.
그래서 int형 배열에도 제대로 저장이 되지 않고, 최종계산도 이상하게 되므로,
계산마다 나눠서 저장해주어야한다.
6. 11659 - DP
https://www.acmicpc.net/problem/11659
해결
#include <iostream>
using namespace std;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
long long N, M;
cin >> N >> M;
int arr[N + 1] = {
0,
};
for (int i = 1; i <= N; i++)
{
cin >> arr[i];
}
int dp[N + 1] = {
0,
};
dp[1] = arr[1];
for (int i = 2; i <= N; i++)
{
dp[i] = dp[i - 1] + arr[i];
}
while(M--)
{
int start, end;
cin >>start>>end;
cout << dp[end]-dp[start]+arr[start] <<"\n";
}
return 0;
}풀이
부분합이라
1부터 N까지의 합을 저장하는 dp를 만들어두고,
start end에 맞게 계산하였다.
쉬웠다.
7. 12852 - DP
https://www.acmicpc.net/problem/12852
1번 DP문제의 변형이다.
경로를 추가로 출력하면 된다.
해결
#include <iostream>
using namespace std;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int N;
cin >> N;
int dp[N + 1] = {
0,
}; // 횟수 최소값
int path[N + 1] = {
0,
}; // 이전 인덱스값
dp[1] = 0;
// dp와 path를 채움, dp[i]와 예상값을 비교하여 더 작은 값을 취하도록 한다.
for (int i = 2; i <= N; i++)
{
dp[i] = dp[i - 1] + 1;
path[i] = i - 1;
if (i % 2 == 0 && dp[i] > dp[i/2] + 1)
{
dp[i] = dp[i/2] + 1;
path[i] = i/2;
}
if (i % 3 == 0 && dp[i] > dp[i/3] + 1)
{
dp[i] = dp[i/3] + 1;
path[i] = i/3;
}
}
cout << dp[N] <<"\n";
cout << N << " ";
int idx = N;
for(int i=0; i<dp[N];i++)
{
cout << path[idx] << " ";
idx = path[idx];
}
return 0;
}
풀이
dp와 path를 채운다.
dp는 최소횟수, path는 다음노드를 의미한다.
위의 식만 구현할 수 있으면 끝.
