1. 피보나치 - 단순 1차
2. 파스칼의 삼각형 -단순 1차
3. 배낭 -
4. 이친수 -이진 DP
5. 인접한 비트의 수 -이진 DP
6. 롤러코스트 - 3차원
7. 집합 -2차원
-----------------------
1. 피보나치 수열
아래와 같은 규칙성을 갖는 수열이 있을 때(피보나치 수열), 임의로 주어지는 n번째 수열 값을 구하시오. (위치 시작은 0)
0 1 1 2 3 5 8 13 ...
D[0] = 0
D[1] = 1
D[i] = D[n-2] + D[n-1]
2. 파스칼의 삼각형
아래 그림과 같은 규칙성을 가진다고 할 때(파스칼의 삼각형), 열번호와 행번호를 주면 해당 번호에 위치한 수를 리턴하는 함수를 제작하시오.
(행과 열번호는 0부터 시작)
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
...
입력: 행번호 열번호
출력: 해당 행,열에 위치한 갓
ex) 입력: 2 1
출력: 2
D[i][j] = (j==0 || j==i) ? 1 : D[i-1][j-1] + D[i-1][j]
3. 배낭
n개의 보석이 있다. 각 보석은 자신의 고유 무게와 가치가 있다. 배낭에 이 보석들을 담는데, 보석들의 가치 총계가 최대가 되게끔 담아라. 단, 배낭에 담을 수 있는 최대무게는 제한되어있다. 즉, 제한된 무게내에서 최대가치가 되게 보석들을 담아야 한다. (담을 수 있는 개수는 제한이 없다.)
w[i]: i번째 보석의 무게, v[i]:i번째 보석의 가치
D[i][j] : 0~i개까지의 보석을 사용하고, j무게 만큼의 제한이 있을 때, 취할 수 있는 최대 보석 가치
D[i][j] = (w[i] < j) ? max(D[i-1][j], D[i-1][j-w[i]] + v[i]) : D[i-1][j]
D[0][j]=0
4. 이친수
0과 1로 이루어진 이진수중 다음 성질을 만족하는 수를 이친수라고 한다.
이친수는 0으로 시작하지 않는다.
이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다.
예를 들면 1, 10, 100 등이 이친수가 된다.
하지만 010이나 110은 각각 1, 2번 규칙에 위배되므로 이친수가 아니다.
N(1≤N≤90)이 주어졌을 때, N자리 이친수의 개수를 구하는 프로그램을 작성하시오.
D[i][0] : 0으로 끝나면서, i번째 자리까지의 이친수 개수
D[i][1] : 1로 " , "
D[0][0] = D[0][1] = 0
D[1][0] = 0, D[1][1] =1
D[i][0] = D[i-1][0] + D[i-1][1]
D[i][1] = D[i-1][0]
5. 인접한 비트의 수
0과 1로 이루어진 수열 S가 있다.
S의 첫 수를 s1, 마지막 수를 sn이라고 할 때, S의 인접한 비트의 개수는 다음과 같이 구할 수 있다.
s1 x s2 + s2 x s3 + s3 x s4 + ... + sn-1 x sn
위의 식을 이용하면 수열 S에서 인접한 1의 개수를 구할 수 있다. 예를들어, 011101101의 인접한 비트의 개수는 3이 되고, 111101101은 4, 010101010은 0이 된다.
수열 S의 크기 n과 k가 주어졌을 때, 인접한 비트의 개수가 k인 수열 S의 개수를 구하는 프로그램을 작성하시오.
예를 들어, n이 5이고, k가 2이면, 수열 S가 될 수 있는 수열은 다음과 같이 6가지가 있다.
11100, 01110, 00111, 10111, 11101, 11011
D[i][j][0] : 0으로끝나면서, i개의 비트를 사용해서, j개의 인접비트수가 되는 수열 개수
D[i][j][1] : 1으로끝나면서, i개의 비트를 사용해서, j개의 인접비트수가 되는 수열 개수
D[1][0][0] = D[1][0][1] = 1
2 <= i <= n, 0 <= j < i --> j를 1부터가 아닌 0부터 시작함에 유의. i비트를 사용해서 인접비트가 0인 수도 계산됨에 유의
D[i][j][0] = D[i-1][j][0] + D[i-1][j][1]
D[i][j][1] = D[i-1][j][0] + D[i-1][j-1][1]
6. 롤러코스트
소들은 롤러코스터를 짓고있다! 소들은 자신들이 가지고 있는 돈을 활용해서 최대한 재밌는 롤러코스터를 만들고 싶어한다.
롤러코스터는 길이 L(1<=L<=1,000)의 직선형 롤러코스터이다. 소들이 롤러코스터를 지을 때 롤러코스터는 N(1<=N<=10,000)개의 교체 가능한 부품들중 일부로 구성되어야 한다.
각 부품i는 고정된 길이 Wi(1<= Wi <= L)를 가지고 있다. 그리고 다양한 지형의 굴곡 때문에, i번째 부품은 오직 Xi(0<= Xi <= L-Wi)의 위치를 시작점으로만 놓을 수 있다.
소들은 다양한 롤러코스터를 0부터 L까지 빈틈없이 채우고 싶어한다. 만약 중간에 빈칸이 있으면 롤러코스터를 구성할 수 없다. 또한 각 부품끼리 겹쳐서 롤러코스터를 건설하는 경우도 없다.
각 i번째 부품은 "재미도" Fi(1<= Fi <= 1,000,000)과 짓는데 드는 비용 Ci(1<= Ci <= 1000)를 가지고 있다. 총 비용은 롤러코스터를 구성하는 부품을의 비용의 합으로 계산된다. 마찬가지로 총 재미도의 합은 롤러코스터를 구성하는 부품들의 재미도의 합으로 계산된다.
소들의 총 예산은 B(1<= B<= 1000)이다. 소들을 도와 예산내에서 가장 큰 재미도를 가진 롤러코스터를 지을 수 있도록 도와주자!
M[i][k]: i가 끝점인 곳에 위치한 k번째 부품 {x,f,c}
D[i][j]: i 길이 까지, j예산내에서 만들 수 있는 최대 재미값
D[i][j]=-1
newVal = D[M[i][k].x][j-M[i][k].c] + M[i][k].f
D[i][j] = (D[i][j]==-1 || D[i][j] < newVal) ? newVal
where
j > M[i][k].c
D[i-M[i][k].x][j-M[i][k].c] != -1
ans = max(D[L][i])
해설
변수가 Wi, Fi, Ci, Xi로 4개이고, 제약조건 "B 언더" "Xi"포지션을 지키면서 F를 최대화하는 문제.
D[i][j]를 i길이까지, j예산내에서 만들 수 있는 최대 재미값으로 놓는데, 여기서 i가 i번째 부품이 아니고, 길이인것이 핵심
따라서, 부품을 놓일 수 있는 위치별로 찾을 수 있게 변환한 배열 필요. 이것이 M[i][j]
즉, M[i][j]는 i가 끝점인 곳에 위치한 k번째 부품 정보(x,f,c).
여기서 i를 끝점으로 한 것은, 문제를 풀 때 0에서부터 전체길이 L까지에 대해서 풀 것인데, 그럴러면 부품의 끝단으로 처리해야 되기때문.
점화식은,
길이 i를 L까지 증가시키면서,
허용비용 j를 B까지 증가시키면서,
해당위치 i에서의 사용가능한 부품 k에 대해서,
이 위치에서의 k부품에 대한 D값을 계산해가면서 최대가 되는 값을 찾아가는 것.
M = M[i][k]라 하면
D[i][j] = max(D[i][j], D[M.x][j-M.c] + M.f) // j-M.c를 한것은, 이번 M이 사용다면, 그 이전 cost인 j-M.c에서 와야기에
#include <stdio.h>
#include <vector>
using namespace std;
struct xyz {
int x, f, c;
};
vector<xyz> M[1001];
int D[1001][1001];
int main(void) {
//freopen("롤러코스트.txt", "r", stdin);
setbuf(stdout, NULL);
int L, N, B;
scanf("%d %d %d", &L, &N, &B);
int x, w, f, c;
for (int i = 0; i < N; ++i) {
scanf("%d %d %d %d", &x, &w, &f, &c);
M[x + w].push_back({x,f,c});
}
for (int i = 0; i <= L; ++i) {
for (int j = 0; j <= B; ++j) {
D[i][j] = -1;
}
}
D[0][0] = 0;
for (int i = 1; i <= L; ++i) {
for (int j = 0; j <= B; ++j) {
for (int k = 0; k < M[i].size(); ++k) {
if (M[i][k].c > j) continue;
if (D[M[i][k].x][j - M[i][k].c] == -1) continue;
if (D[i][j] == -1 || D[i][j] < D[M[i][k].x][j - M[i][k].c] + M[i][k].f)
D[i][j] = D[M[i][k].x][j - M[i][k].c] + M[i][k].f;
}
}
}
int ans = -1;
for (int i = 0; i <= B; ++i) {
if (D[L][i] == -1) continue;
if (D[L][i] > ans) ans = D[L][i];
}
printf("%d", ans);
return 0;
}
7. 집합
집합 A와 B에 각각 N, M개의 자연수가 들어있다. 이제 다음의 행동을 min(N, M)번 시행할 것이다.
집합 A, B에서 각각 자연수 하나씩 고르고, 고른 수는 각 집합에서 삭제한다
고른 두 수의 차를 집합 C에 넣는다.
우리의 목표는 집합 C에 있는 원소의 합을 최소로 하는 것이다.
핵심
- 두 집합을 소팅
- 같이 차례대로 빼내야 함.
D[i][j] : A에서 1~i까지, B에서 1~j까지 사용했을 때, 최소 합
D[i][j] = D[i-1][j-1] + abs(A[i] - B[j])
if(i>j && D[i][j] > D[i-1][j]) D[i][j] = D[i-1][j]
if(i<j && D[i][j] > D[i][j-1]) D[i][j] = D[i][j-1]
해설
두 집합 중 작은 집합의 원소 갯수 만큼만을 뺀다는 것에 주의. 즉, min(N,M)만큼인데, 따라서 많이 있는 집합쪽에는 빼는 데 사용되지 않은 원소가 남아 있을 수 있다는 것. 해서, 기본적으로는 A의 한칸 왼쪽것과 B의 한쪽 왼칸 것을 빼는 것이 정상이지만, 한 쪽이 더 많이 진행되었다면(i>j or i<j), 많이 진행된 쪽의 이전 값(D[i-1][j] or D[i][j-1]과 비교해줘야 함.
소스
#include <stdio.h>
#include <algorithm>
#include <math.h>
using namespace std;
const int MAX = 1003;
int N, M;
int A[MAX] = { 0 }, B[MAX] = { 0 };
int D[MAX][MAX];
int main()
{
//freopen("집합.txt", "r", stdin);
setbuf(stdout, NULL);
scanf("%d%d", &N, &M);
for (int i = 1; i <= N; ++i) scanf("%d", &A[i]);
for (int i = 1; i <= M; ++i) scanf("%d", &B[i]);
sort(A + 1, A + 1 + N);
sort(B + 1, B + 1 + M);
for (int i = 1; i <= N; ++i) {
for (int j = 1; j <= M; ++j) {
D[i][j] = D[i - 1][j - 1] + abs(A[i] - B[j]);
if (i > j && D[i][j] > D[i-1][j]) D[i][j] = D[i - 1][j];
if (i<j && D[i][j] > D[i][j - 1]) D[i][j] = D[i][j - 1];
}
}
printf("%d", D[N][M]);
return 0;
}
-끝-
'알고리즘 > 알고리즘 노트' 카테고리의 다른 글
| [다이나믹]-문제3 (0) | 2016.07.30 |
|---|---|
| [다이나믹]-문제2 (0) | 2016.07.30 |
| [문자열] (0) | 2016.07.28 |
| [자료구조] (0) | 2016.07.27 |
| [다이나믹]타일채우기 문제들 (0) | 2016.07.26 |