카드 구매하기1 _ 최대값
https://www.acmicpc.net/problem/11052
N개의 카드를 구매해야한다.
카드팩은 총 N가지 종류가 존재한다.
i번째 카드팩은 i개의 카드를 담고 있고,카드팩의 가격은 P[i]원이다.
카드 N개를 구매하는데 드는 비용의 최대값을 구하는 문제.
점화식 :
D[N] = 카드 N개를 구매하는 비용의 최대값.
마지막 카드 팩에 집중하려 한다. 마지막 카드 팩에는 몇개의 카드가 들어 있을까? -> 알수없음.
DP에서 알수없다라는 정보는 좋은 정보. i개 있었다고 가정.
카드팩 + 카드팩 + ... + 마지막 카드팩 = N개의 카드
카드팩 + 카드팩 + ... + i개 = N개의 카드
N-i개 + i개 = N개의 카드
D[N] = D[N-i] + P[i] 최대 비용.
D[N] = max(D[N-i] + P[i]) (1 <= i <= N)
시간복잡도 : 문제의 개수 x 하나의 칸을 채우기 위해서 필요한 시간 (총 최대 N개의 수를 비교하여 최대값을 찾고 있음.)
N x N = O(N^2)
for (int i=1; i<=N; i++){
for(int j=1; j<=i; j++)
d[i] = max(d[i], d[i-j] + p[j]);
}이 방법에서 배열 d의 초기값은 항상 0이다.
카드 구매하기2 _ 최소값
https://www.acmicpc.net/problem/16194
최대값을 구하는 문제 처럼 푼다면, 배열의 초기값을 잘 설정해주어야 한다.
카드를 구매하는 비용이 항상 0보다 크기 때문에 최소값의 결과는 항상 0이 되기 때문이다.
첫번째 방법.
문제에서 주어진 최대값으로 초기화 하기. d[i] = 1000*10000;
for (int i=1; i<=N; i++)
d[i] = 1000*10000;
for (int i=1; i<=N; i++){
for(int j=1; j<=i; j++)
d[i] = min(d[i], d[i-j] + p[j]);
}두번째 방법.
음수로 초기화 하기(카드 값은 음수가 나올 수 없기 때문임). d[i] = -1
for (int i=1; i<=N; i++)
d[i] = -1;
for (int i=1; i<=N; i++){
for(int j=1; j<=i; j++) {
if(d[i] == -1 | d[i] > d[i-j] + p[j])
d[i] = d[i-j] + p[j];
}
}1,2,3 더하기5
https://www.acmicpc.net/problem/15990
정수 n을 1,2,3의 합으로 나타내는 방법의 수를 구하는 문제.
단, 같은 수를 두 번 이상 연속해서 사용하면 안됨. (추가된 조건)
연속 -> 2개씩 나누어 생각한다.
증가, 감소도 같은 방식으로 생각하면 된다.
두 번 이상 연속 되는 것을 제거하려면 어떤 수를 사용할 때, 그 앞의 수는 어떤 수를 제외한 나머지를 사용하면 된다.
점화식 : D[i][j] = i를 1,2,3의 합으로 나타내는 방법의 수 마지막에 사용한 수는 j
D[i][1] = i를 1,2,3의 합으로 나타내는 방법의 수 마지막에 사용한 수는 1
-> 바로 전에 사용할 수 있는 수 : 2,3 D[i-1][2] + D[i-1][3]
D[i][2] = i를 1,2,3의 합으로 나타내는 방법의 수 마지막에 사용한 수는 2
-> 바로 전에 사용할 수 있는 수 : 1,3 D[i-1][1] + D[i-1][3]
D[i][3] = i를 1,2,3의 합으로 나타내는 방법의 수 마지막에 사용한 수는 3
-> 바로 전에 사용할 수 있는 수 : 1,2 D[i-1][1] + D[i-1][2]
초기화
1,2,3 더하기문제처럼 D[0] = 1 (아무것도 없는 것도 센다) 으로 초기화 하게 되면 중복이 발생함.
D[0][1] = 1, D[0][2] = 1, D[0][3] = 1로 초기화 할 경우,
D[1][1] = D[0][2] + D[0][3] = 2 (중복 발생)
따라서 예외 처리를 해야함.D[i][1],
i > 1 : D[i-1][2] + D[i-1][3]
i == 1 : 1
i < 1 : 0
쉬운 계단 수
https://www.acmicpc.net/problem/10844
인접한 자리의 차이가 1이 나는 수를 계단수라고 한다.
숫자의 범위는 0 ~ 9이다.
EX) 7898987
길이가 N인 계단 수의 개수를 구하는 문제이다.
인접한 자리 = 연속한 수
점화식 : D[N][L] = 길이가 N인 계단수, 마지막 수는 L
_ _ _ _ _ ... (L-1 or L+1) L
1 2 3 4 5 ... N-1 번째 수 N번째 수
D[N][L] = D[N-1][L-1] + D[N-1][L+1]
단, L = 0인 경우와 L = 0인 경우는 제외해야한다.
for (int j=1; j<=9; j++) d[1][j] = 1; // 길이가 1인 경우,
for (int i=2; i<=n; i++) {
for (int j=0; j<=9; j++) {
d[i][j] = 0;
if (j-1 >= 0) d[i][j] += d[i-1][j-1];
if (j+1 <= 9) d[i][j] += d[i-1][j+1];
d[i][j] %= mod; // 나머지 연산 중
}
}
long long ans = 0;
for (int i=0; i<=9; i++) ans+=d[n][i];
ans %= mod; // 나머지 연산 중이친수
https://www.acmicpc.net/problem/2193
방법 1 - 2차원 DP
0과 1로만 이루어진 수를 이진수라고 한다.
여기서 만약 다음의 조건을 만족하면 이친수라고 한다.
- 이친수는 0으로 시작하지 않는다.
- 이친수에서 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 가지지 않는다.
N자리 이친수의 개수를 구하는 문제
점화식 : D[N][L] = N자리 이친수, 마지막 수 L
- D[N][0] = D[N-1][0] + D[N-1][1]
N-1 (1,0) , N (0) - D[N][1] = D[N-1][0]
N-1 (0) , N (1)
초기값 : 길이가 가장 짧은 이친수는 길이가 1이다.
D[1][0] = 0
D[1][1] = 1
답 : 0으로도 끝날 수도 있고, 1로도 끝날 수도 있기 때문에 1,2번을 합한다.
D[N][0] + D[N][1]
방법 2 - 1차원 DP
마지막이 0과 1인 경우 두 가지만 존재하기 때문에 일차원 DP로 문제 푸는 것이 가능하다.
점화식 : D[N] = N자리 이친수의 개수
1. 마지막 수가 0으로 끝나는 경우
N-1번째 수가 0도 되고 1도 된다.
따라서 D[N-1]이다.
2. 마지막 수가 1으로 끝나는 경우
N-1번째 수가 0만 된다. N-2번째는 0과 1이 모두 올 수 있다.
따라서 D[N-2]이다.
D[N] = D[N-1] + D[N-2]
