1. 행렬곱 순서
2. prime - 최대공약수가 1인 수열 개수
3. 가장 긴 증가하는 부분 수열
4. 교차하지 않는 원의 현들의 최대집합 (백준 2673)
5. 식당 (백준 6101)
6. 김치배달(백준2184)
7. 1,2,3 더하기 (백준 9095)
8. 동전 바꿔주기 (백준 2624)
9. 내리막 길 (백준 1520)
-------------------------------
1. 행렬곱 순서
풀이.
DP로 풀어야 한다.
D[i][j]: i번째 행렬에서부터 j번째 행렬까지의 최소 곱
D[i][j] = min(D[i][k] + D[k+1][j] + P[i-1] * P[k] * P[j]), i<= k <j
D[i][j] = 0 , when i == j
위 식의 나오게 된 배경은,
행렬 A1, A2, ... An 이 있고,
A1 = p0 x p1, A2=p1 x p2, ... An=pn-1 x pn 이라할 때,
(A1~Ak)과 (Ak+1 ~ An)까지의 곱으로 나눠서 생각할 수 있고, 각각의 최소값을 구한다는 개념.
이 때 두 그룹의 각각 최소값인 D[i][k]와 D[k+1][j]를 더하고, 또한 두 그룹을 곱하면서 나오는 연산횟수인 P[i-1] * P[k] * P[j]를 더해서 최솟값을 구해야 함.(행렬 P0 x P1 과 P1 x P2를 곱하면, P0 x P1 x P2 만큼의 연산이 발생)
위 점화식을 다이나믹 프로그래밍 해야는데, 코드는 아래와 같다.
for (int r = 1; r <= (N - 1); ++r) {
for (int i = 1; i <= (N - r); ++i) {
int j = i + r;
int low = INT_MAX;
int minK;
for (int k = i; k < j; ++k) {
int tmp = D[i][k] + D[k + 1][j] + P[i - 1] * P[k] * P[j];
if (tmp < low) {
low = tmp;
minK = k;
}
}
D[i][j] = low;
T[i][j] = minK;
}
}
위 코드에서, r값을 변화시키는 것에 주의. 이 r값은, 몇 개만큼의 행렬을 묶어서 계산해보느냐를 나타냄. 즉, r이 1이면, (A1 x A2), (A2 x A3), (A3 x A4) ...처럼 해보는 것이고 (i를 증가시키면서)
r=2이면, (A1 x A2 x A3), (A2 x A3 x A4) ... 이렇게 해보는 것.
중간에 minK값을 보관한 것은, 행렬들의 곱 순서를 보관하기 위해서임. 이 테이블 T를 보고서, 실제 행렬곱 순서를 정할 수 있음.
예를 들어 행렬 A1, A2, A3 가 있을 때, 계산결과 T테이블 값이 다음과 같이 도출되었다 하자.
T[1][2] = 1, T[2][3] = 2, T[1][3] = 2 나머지는 갱신안되어 zero
이것은 (A1A2)A3 로 계산되어야한다는 것을 의미한다.
T[1][2]=1이므로 그냥 A1A2가 계산. T[2][3]=2이므로 A2다음에 끊는다는 얘기므로 그대로 A2A3.
T[1][3]=2은 A1~A3까지의 곱에서 A2다음에 끊는다는 얘기므로, (A1A2)A3
이러한 곱셈순서를 괄호로 프린트하려면 다음과 같이 하면 된다. (재귀호출. 잘 외두두기 바람)
void print_array(int i, int j) {
if (i == j) printf("A%d", i);
else {
printf("(");
print_array(i, T[i][j]);
print_array(T[i][j] + 1, j);
printf(")");
}
}
또한 이 T 테이블을 이용해서, 실제 곱셈을 효율적인 순서대로 할 수 있다.
vector<vector<int> > doMulti(vector<vector<int> > a, vector<vector<int> > b) {
int p, q, r;
p = a.size();
q = b.size();
r = b[0].size();
vector<vector<int> > c(p,vector<int>(r,0));
for (int i = 0; i < p; ++i) {
for (int j = 0; j < r; ++j) {
c[i][j] = 0;
for (int k = 0; k < q; ++k) {
c[i][j] += a[i][k] * b[k][j];
}
}
}
return c;
}
vector<vector<int> > multi(int i, int j) {
if (i == j) return v[i];
return doMulti(multi(i,T[i][j]), multi(T[i][j]+1,j));
}
전체 소스.
#include <stdio.h>
#include <limits.h>
#include <vector>
#include <algorithm>
#define MAX 503
#define min(a,b) ((a) < (b) ? (a) : (b))
using namespace std;
struct xy {
int x, y;
xy(int _x, int _y) { x = _x; y = _y; }
};
typedef pair<xy, int> xyi;
int N;
int P[MAX + 5];
int D[MAX][MAX];
int T[MAX][MAX];
vector<vector<int> > v[MAX];
void print_array(int i, int j) {
if (i == j) printf("A%d", i);
else {
printf("(");
print_array(i, T[i][j]);
print_array(T[i][j] + 1, j);
printf(")");
}
}
vector<vector<int> > doMulti(vector<vector<int> > a, vector<vector<int> > b) {
int p, q, r;
p = a.size();
q = b.size();
r = b[0].size();
vector<vector<int> > c(p,vector<int>(r,0));
for (int i = 0; i < p; ++i) {
for (int j = 0; j < r; ++j) {
c[i][j] = 0;
for (int k = 0; k < q; ++k) {
c[i][j] += a[i][k] * b[k][j];
}
}
}
return c;
}
vector<vector<int> > multi(int i, int j) {
if (i == j) return v[i];
return doMulti(multi(i,T[i][j]), multi(T[i][j]+1,j));
}
int main() {
freopen("행렬곱.txt", "r", stdin);
scanf("%d", &N);
for (int i = 0; i <= N; ++i) {
scanf("%d %d", &P[i], &P[i + 1]); //주의
}
for (int r = 1; r <= (N - 1); ++r) {
for (int i = 1; i <= (N - r); ++i) {
int j = i + r;
int low = INT_MAX;
int minK;
for (int k = i; k < j; ++k) {
int tmp = D[i][k] + D[k + 1][j] + P[i - 1] * P[k] * P[j];
if (tmp < low) {
low = tmp;
minK = k;
}
}
D[i][j] = low;
T[i][j] = minK;
}
}
printf("%d\n", D[1][N]);
print_array(1, N);
return 0;
}
2. prime
어떤 수열 S가 주어진다. 수열 S에서 한 개 이상 원소를 선택했을 때, 선택한 수 혹은 수들의 최대공약수가 1이 되는 것의 개수를 구하는 프로그램을 작성하시오.
입력
첫 번째 줄에 수열의 크기 N이 주어진다. (1 ≤ N ≤ 100)
두 번째 줄부터 N개의 줄에 걸쳐 수열의 각 원소 Si가 주어진다. 어떤 두 원소가 같을 수 있다. (1 ≤ Si ≤ 100,000)
출력
첫 번째 줄에 정답을 10,000,003으로 나눈 나머지를 출력한다.
힌트
입력 예제
3
2
4
3
출력 예제
3
예제 설명
주어진 수를 이용해서 선택하는 모든 방법을 나열하면 아래와 같다.
{2} : 최대공약수는 2이다.
{3} : 최대공약수는 3이다.
{4} : 최대공약수는 4이다.
{2, 3} : 최대공약수는 1이고, 답이 되는 경우 중 한 가지가 된다.
{2, 4} : 최대공약수는 2이다.
{3, 4} : 최대공약수는 1이고, 답이 되는 경우 중 한 가지가 된다.
{2, 3, 4} : 최대공약수는 1이고, 답이 되는 경우 중 한 가지가 된다.
즉, 총 3가지의 경우가 존재한다.
풀이
....어려움
소스
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
#define M 10000003
vector<int> v[100002];
int n, s[102], d[102][100002], ans;
int gcd(int a, int b) {
if (a > b) return gcd(b, a);
if (b%a == 0) return a;
else return gcd(b%a, a);
}
int main() {
freopen("prime.txt", "r", stdin);
int i, j, k;
scanf("%d", &n);
for (i = 1; i <= n; i++) scanf("%d", &s[i]);
sort(s + 1, s + n + 1);
//각 수에 대해 약수 구하기
for (i = 1; i <= s[n]; i++) {
for (j = 1; j*j <= i; j++) {
if (i%j == 0) {
v[i].push_back(j);
if (j*j != i) v[i].push_back(i / j);
}
}
}
//d[i][j]: 1번째 수에 대해, 1~i까지의 gcd=j인 갯수
for (i = 1; i <= n; i++) {
d[i][s[i]] = 1; //자기자신
for (j = 1; j<i; j++) {
for (k = 0; k<v[s[j]].size(); k++) {
int t = v[s[j]][k];
if (gcd(t, s[i]) == 1) {
d[i][1] += d[j][t]; //핵심
d[i][1] %= M;
}
else d[i][gcd(t, s[i])] += d[j][t], d[i][gcd(t, s[i])] %= M;
}
}
ans += d[i][1]; ans %= M;
}
printf("%d", ans);
return 0;
}
3. 가장 긴 증가하는 부분 수열 (백준 11053번)
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.
예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.
입력
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.
둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)
출력
첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.
예제 입력
6
10 20 10 30 20 50
예제 출력
4
핵심
- i번째에 대한 DP를 세우는 것이 아니고, 수열값 1~1000에 대해서 DP세워야 함
- D[i] : i 값에 대해 0~i 까지에 대한 최대 증가 수열 크기. ex)D[4]: 값 4에 대한 최대증가수열 크기
- D[i] = max(D[0]~D[3]) + 1
- D[A[1]] = 1
소스
#include <stdio.h>
int N;
int A[1001], D[1001];
int main() {
scanf("%d", &N);
for (int i = 1; i <= N; ++i) scanf("%d", &A[i]);
int max=1;
D[A[1]] = 1;
for (int i = 2; i <= N; ++i) {
int M = 0;
for (int j = 0; j <= A[i]-1; ++j) if (D[j] > M) M = D[j];
D[A[i]] = M + 1;
if (max < D[A[i]]) max = D[A[i]];
}
printf("%d\n", max);
return 0;
}
4. 교차하지 않는 원의 현들의 최대집합 (백준 2673)
평면상에 있는 원의 둘레에 100개의 점이 일정한 간격으로 시계방향으로 번호가 1, 2, ... 100으로붙여져 있다. 이 점들을 끝점으로 갖는 N개의 선분(원의 현)이 입력으로 주어질 때, 이들중에서 서로 교차하지 않는 것들을 최대한 많이 찾아서 그 개수를 출력하는 프로그램을 작성하라.
단, 1≤N≤50이고, 주어진 각 점은 많아야 한 현의 끝점이 될 수 있다.
입력
첫번째 줄은 주어지는 현의 개수 N이고, 다음의 N줄은 각 현의 양끝점의 번호가 주어진다.
출력
구한 현의 개수를 출력한다.
예제 입력
5
97 31
1 45
27 5
11 65
43 72
예제 출력
3
풀이
- 1~100까지의 수직선상에서, 서로 겹치지않게 영역을 지정하는 문제와 동일 (1과 100사이를 칼로 잘라 선분을 만들어서 생각)
- D[i][j]: 점 i~j까지에서의 겹치지않는 현 최대 갯수
- D[i][j] = Max(D[i][k-1] + D[k+1][j-1] + q[k][j]), i<=k<=j
q[k][j]: 점 k와 j를 잇는 선분이 있으면 1, 없으면 0
-최적행렬곱에 대한 DP풀이 처럼, i~j사이를 1,2,3씩 증가시키면서 계산
소스
#include <stdio.h>
#define max(a,b) ((a) > (b)) ? (a) : (b)
int N;
int q[101][101]; //q[i][j]: 수직선상의 점 i에서 j로의 선이 있으면 1, 없으면 0
int D[101][101]; //D[i][j]: 점i에서 j까지 범위에서 가질 수 있는 중보없는 최대 현 갯수. D[1][100]=?
//D[i][j] = Max(D[i][k-1] + D[k+1][j-1] + q[k][j]) i <= k <= j
int main() {
scanf("%d", &N);
int s,e;
for (int i = 1; i <= N; i++) {
scanf("%d%d", &s, &e);
if (s < e) q[s][e] = 1;
else q[e][s] = 1;
}
for (int d = 1; d <= 99; ++d) { //i와 j 사잇 길이: 1~99
for (int i = 1; i <= (100 - d); ++i) {
int j = i + d;
for (int k = i; k <= j; ++k) D[i][j] = max(D[i][j], D[i][k - 1] + D[k + 1][j - 1] + q[k][j]);
}
}
printf("%d\n", D[1][100]);
return 0;
}
5. 식당 (백준 6101)
농부 존의 식당은 N마리의 소들에게 M개의 음식을 제공해 주고 있다.
소들은 자신들이 선호하는 음식 Pi를 가지고 있는데, 농부 존은 다음 방법으로 소들에게 음식을 공급한다.
들어오는 소들을 순서대로 그룹으로 나눈다. [1 ~ 4] / [5 ~ 7] / [8 ~ 10] 이런 식으로.
그룹에 있는 소들에게 음식을 제공하는 데 드는 비용은 (해당 그룹에서 선호하는 음식의 합집합 크기)^2 이다. 음식을 수로 생각하면, 서로 다른 수들의 개수의 제곱이다.
최소 비용으로 음식을 제공하려면 어떻게 해야 할까?
입력
첫번째 줄에 N, M이 주어진다. (1 <= M <= N <= 40000)
이후 N개의 줄에 Pi가 주어진다. (1 <= Pi <= M)
출력
최소 비용을 출력하라.
예제 입력 복사
13 4
1
2
1
3
2
2
3
4
3
4
3
1
4
예제 출력
11
힌트
[1] [2] [3] [4] [5, 6] [7, 8, 9, 10, 11] [12] [13] 과 같이 묶으면, 1 + 1 + 1 + 1 + 1 + 4 + 1 + 1 = 11의 비용이 든다.
풀이
D[i]: i부터 N까지 최소비용
D[N]=1, D[1]=?
B(i,j) : i에서 j까지를 한 박스에 담았을 때 비용
D[i] = Min(B(i,i+j)+D[i+j+1]), 0 <= j <= N-i
where, B(i,i+j) < (N-i+1)
if(cnt == M) D[i] = min(D[i], cnt * cnt)
- 핵심은 B(i,i+k)를 상수시간에 찾을 수 있어야 함. (아래 소스 참조)
또한, j를 증가시키며(박스에 담는 수를 증가시키며) min값을 찾을 때, B(i,i+j) >= (N-i+1) 가되면 더 이상 박스에 담을 필요 없음.
그리고, 한박스내 가짓수를 나타내는 cnt가 전체 가짓수 M과 같아지면, 하나씩 j를 증가시켜봐야 의미없고, 모두 한 박스에 넣었을 때랑 비교
#include <stdio.h>
#define MAX 987654321
int N, M, i,j, flag = 0, square, cnt;;
int p[40001], D[40002], T[40002];
int main() {
scanf("%d%d", &N, &M);
for (i = 1; i <= N; ++i) scanf("%d", &p[i]);
D[N] = 1;
for (i = N - 1; i >= 1; --i) {
++flag; cnt = 0; D[i] = MAX;
for (j = 0; j <= (N - i); ++j) {
if (T[p[i + j]] != flag) {
cnt++; square = cnt * cnt;
T[p[i + j]] = flag;
if ((square) >= (N - i + 1)) break;
if (cnt == M) {
if (square < D[i]) D[i] = square; break;
}
}
if ((square + D[i + 1 + j]) < D[i]) D[i] = square + D[i + 1 + j];
}
}
printf("%d\n",D[1]);
return 0;
}
6. 김치 배달(백준 2184번)
월드 식품에서는 김치를 만들어 여러 도시들에 배달 판매하는 일을 하고 있다. 각각의 도시들과 김치 공장은 1차원 직선상의 점에 위치해 있다. 각 도시는 정수 좌표로 나타난다.
배달을 할 때에는 공장에서 N(1≤N≤1,000)포기의 김치를 들고 시작한다. 그리고 1차원 직선을 따라 왼쪽이나 오른쪽으로 움직인다. 이동을 할 때에는 1초에 한 칸씩 움직일 수 있다. 또한 어떤 도시에 도착했을 때 김치는 0의 시간에 배달되는 것으로 생각한다. 즉 도시에 도착하기만 하면 배달이 완료되는 것으로 생각한다. 또한 김치를 배달하는 순서는 상관이 없다.
각각의 김치는 모두 t=0 의 시각에 공장에서 출발된다. 각각의 김치는 1초에 1만큼씩 쉬게 되는데, 김치가 쉬게 될 경우 소비자가 불만을 토로할 수 있다. 따라서 월드 식품에서는 각 도시에 김치가 도착했을 때의 김치의 쉰 정도의 합을 최소로 하려 한다.
각 도시의 위치 및 김치 공장의 위치(x좌표)가 주어졌을 때, 모든 도시에 김치를 배달할 때의 김치의 쉰 정도의 합의 최소값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 두 정수 N, L이 주어진다. L은 김치 공장의 x좌표이다. 다음 N개의 줄에는 김치를 배달할 도시의 x좌표가 주어진다. 모든 좌표는 1이상 1,000,000이하의 정수이다.
출력
첫째 줄에 답을 출력한다.
예제 입력 복사
4 10
1
9
11
19
풀이
D[i][j][k]: i번째 도시에서 j번째 도시까지 배달완료하고, k(0:left, 1:right) 위치일때, 남아있는 도시배달 최솟값
D[0][N][k] = 0, D[S][S][0]=?
D[i][j][k][r] =
cur = (k==0) ? p[i] : p[j];
min(D[i-1][j][0][r-1] + d(cur,p[i-1]) * r, D[i][j+1][1][r-1] + d(cur,p[j+1]) * r
- 출발점까지 넣어서 소팅을 한 후, 출발점에 대한 인덱스는 이분탐색으로 찾는다. (N이 1000이므로, 이분탐색 안해도 무방)
- 점화식을 세울 때, 처리된 비용 최솟값이 아닌, 남아 있는 최솟값으로 해서 식을 세우는 것이 핵심.
- 일직선상이기에 다음 사항이 자명한 것을 이용
. 종료하는 지점은, 왼쪽 끝이거나, 오른 쪽 끝
. 처음 시작점에서 출발하여 왼쪽 혹은 오른쪽으로 진행. 왼쪽으로는 0이될때까지, 오른쪽으로는 N까지 진행(전체 N번 진행됨: 0~N까지의 선분 수)
- 김치가 쉬는 정도는 누적되어 계산되기에, D[S][S][0]와 D[S-1][S][0]와의 차이는 d(S-1,S) * N
--> 즉, 처음 거리는 N번 영향을 줌. 이것을 반영하기 위해, 변수 r의 처음값을 N으로 두고, 재귀함수를 콜할 때 하나씩 낮춰 줌
소스
#include <stdio.h>#include <algorithm>#define d(a,b) ( ((a)>(b)) ? ((a)-(b)) : ((b)-(a)))#define min(a,b) (((a)<(b)) ? (a) : (b))#define MAX 987654321using namespace std;int N, L, S; //S: L's index after sortingint p[1003];int D[1003][1003][2];/*D[i][j][k]: i번째 도시에서 j번째 도시까지 배달완료하고, k(0:left, 1:right) 위치일때, 남아있는 도시배달 최솟값D[0][N][k] = 0, D[S][S][0]=?D[i][j][k][r] = cur = (k==0) ? p[i] : p[j]; min(D[i-1][j][0][r-1] + d(cur,p[i-1]) * r, D[i][j+1][1][r-1] + d(cur,p[j+1]) * r*///i:left, j:right, k:flag, r:remained int solve(int i,int j, int k, int r){ if (i == 0 && j == N) return 0; if (D[i][j][k]) return D[i][j][k]; D[i][j][k] = MAX; int cur = (k == 0) ? p[i] : p[j]; if (i > 0) D[i][j][k] = solve(i - 1, j, 0, r - 1) + d(cur,p[i-1]) * r; if (j < N) D[i][j][k] = min(D[i][j][k], solve(i,j+1,1,r-1) + d(cur,p[j+1]) * r); return D[i][j][k];}int findIdx(int s, int e){ int m; while (s <= e){ m = (s + e) / 2; if (p[m] == L) return m; if (p[m] < L) s = m + 1; else e = m - 1; } return s;}int main(){ //freopen("김치배달.txt", "r", stdin); scanf("%d%d", &N, &L); p[0] = L; for (int i = 1; i <= N; ++i) scanf("%d", &p[i]); sort(p, p + N + 1); S = findIdx(0, N); printf("%d\n", solve(S,S,0,N));}7. 1,2,3 더하기 (백준 9095)
정수 4를 1, 2, 3의 조합으로 나타내는 방법은 총 7가지가 있다.
1+1+1+1
1+1+2
1+2+1
2+1+1
2+2
1+3
3+1
정수 n이 주어졌을 때, n을 1,2,3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.
입력
첫쨰 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.
출력
각 테스트 케이스마다, n을 1,2,3의 합으로 나타내는 방법의 수를 출력한다.
예제 입력
3
4
7
10
예제 출력
7
44
274
풀이
D[i]: 숫자 i에 대한 1,2,3의 덧셈 조합으로 만들 수 있는 갯수
D[1]=1, D[2]=2 (1+1,2), D[3]=4 (1+1+1, 1+2, 2+1, 3)
D[4]를 고민해봤을 때, 각 조합을 이렇게 생각할 수 있다.
- 1을 제일먼저 놨을 때, 2를 제일 먼저 놨을 때, 3을 제일 먼저 놨을 때.
1을 제일먼저 놓으면 뒷 부분의 합은 '3'이 되야되는 조합임. 즉,
1 + {합이 3이되는 조합} = 1 + (1+1+1), 1+(1+2), 1+(3) -> D[3] = 4
2 + {합이 2가되는 조합} = 2 + (1+1), 2+ (2) -> D[2] = 2
3 + {합이 1이되는 조합} = 3 + (1) -> D[1] = 1
- 해서 답은 7
따라서, D[i]에 대해서도 똑깥이 생각해 보면,
D[i] = D[i-1] + D[i-2] + D[i-3], 4 <= i <= N
소스
#include <stdio.h>int T,N,D[11];int main() { int i, j; scanf("%d", &T); D[1] = 1; D[2] = 2; D[3] = 4; while(T--){ scanf("%d", &N); for (i = 4; i <= N; ++i) D[i] = D[i - 1] + D[i - 2] + D[i - 3]; printf("%d\n", D[N]); } return 0;}8. 동전 바꿔주기 (백준 2624)
명보네 동네 가게의 현금 출납기에는 k 가지 동전이 각각 n1, n2, … , nk개 씩 들어있다. 가게 주인은 명보에게 T원의 지폐를 동전으로 바꿔 주려고 한다. 이때, 동전 교환 방법은 여러 가지가 있을 수 있다. 예를 들어, 10원 짜리, 5원 짜리, 1원 짜리 동전이 각각 2개, 3개, 5개씩 있을 때, 20원 짜리 지폐를 다음과 같은 4가지 방법으로 교환할 수 있다.
20 = 10×2
20 = 10×1 + 5×2
20 = 10×1 + 5×1 + 1×5
20 = 5×3 + 1×5
입력으로 지폐의 금액 T, 동전의 가지 수 k, 각 동전 하나의 금액 pi와 개수 ni가 주어질 때 (i=1, 2,…, k) 지폐를 동전으로 교환하는 방법의 가지 수를 계산하는 프로그램을 작성하시오. 방법 의 수는 231을 초과하지 않는 것으로 가정한다.
입력
첫째 줄에는 지폐의 금액 T(0＜T≤10,000), 둘째 줄에는 동전의 가지 수 k(0＜k≤100), 셋째 줄부터 마지막 줄까지는 각 줄에 동전의 금액 pi(0＜pi≤T)와 개수 ni(0＜ni≤1,000)가 주어진다. pi와 ni사이에는 빈칸이 하나씩 있다.
출력
첫째 줄에 동전 교환 방법의 가지 수를 출력한다. 방법이 없을 때는 0을 출력한다.
예제 입력
20
3
5 3
10 2
1 5
예제 출력
4
풀이
1. 2차원배열이용
- D(i,j): 1~i개까지 동전을 이용해서, j금액을 만들 수 있는 최대 가짓수
- D(i,t*p(i)) = 1, 1<=t*p(i)<=T ;i번째 동전만을 가지고 만들 수 있는 가짓수를 계산해 놓고,
D(i,j) = Sum(D(i-1,j-t*p(i)), 2<=i<=N, 0<=t<=n(i) && 0<=t<=j/p(i)
- 즉, i-1번째 동전까지를 사용했을 때의 D값이 이미 계산되어 있다고 가정하면, i번째 동전에 대해서는, i번째 동전을 사용하던지 말던지의 경우가 생김. 사용하지 않는다면 D(i-1,j)와 같게 되는 것이고, 사용한다면 1개일지 2개일 지 등 사용갯수에 따라 경우수 늘어나게 될 것임
따라서, 이를 수식으로 표현한것이 Sum(D(i-1,j-t*p(i))
2. 1차원배열 이용
-1차원배열을 이용해서 풀수도 있다. 소스 참조
소스-2차원배쳘
#include <stdio.h>int T, k;int p[101], n[101], D[101][10001];int main() { int i, j, t; int t1, t2; scanf("%d%d", &T, &k); for (i = 1; i <= k; ++i) scanf("%d%d", &p[i], &n[i]); for (i = 1; i <= k; ++i) for (t = 1; (t <= n[i]) && (t*p[i]<=T); ++t) D[i][t*p[i]] = 1; for (i = 2; i <= k; ++i) for (j = 1; j <= T; ++j) for (t = 0; (t*p[i] <= j) && (t <= n[i]); ++t) D[i][j] += D[i-1][j-t*p[i]]; printf("%d\n",D[k][T]); return 0;}
소스-1차원
#include <stdio.h>int T,k,D[10001]={1,};int main() { int i,j,t,s,p,n; scanf("%d%d",&T,&k); for(i=1;i<=k;++i){ scanf("%d%d",&p,&n); for (j=T;j>=p;--j){ s=0; for(t=1;t<=n && t*p<=j;++t) s+=D[j-t*p]; D[j]+=s; } } printf("%d\n",D[T]); return 0;}9. 내리막 길 (백준 1520)
여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다.
현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로만 이동하여 목표 지점까지 가고자 한다. 위와 같은 지도에서는 다음과 같은 세 가지 경로가 가능하다.
지도가 주어질 때 이와 같이 제일 왼쪽 위 지점에서 출발하여 제일 오른쪽 아래 지점까지 항상 내리막길로만 이동하는 경로의 개수를 구하는 프로그램을 작성하시오.
풀이
- Bottom up으로 풀지 못할 듯하다. 끝에서 재귀호출하며 메모이제이션하는게 속편함
- 상하좌우에서 접근 가능한데, 단 큰 수에서 작은 수로만 이동할 수 있다는 것이 제약조건이기에, 점화식을 다음과 같이 세울 수 있음
D(y,x): y행 x열까지의 최대 경우의 수. D(M,N)=?
D(y,x) = Sum( D(y+dy[k], x+dx[k])), when T(y+dy[k],x+dx[k]) > T(y,x), 1<=y<=M, 1<=x<=N, 0<=k<=3
dy={{-1,1,0,0}}, dx={0,0,-1,1}
- 위와같이 상하좌우에서 접근가능하도록 점화식을 세울 때 두려움은, 갔던 곳의 값이 다시 되먹임되어 합산되지 않을까 하는 두려움. 근데, 방향성이 수가 큰 곳에서 작은 곳이기에, A->B로 갈 수 있었다면 A<-B로는 못가기에 걱정하지 않아도 됨.
소스
#include <stdio.h>int M,N;int dy[4]={-1,1,0,0},dx[4]={0,0,-1,1},t[502][502],D[502][502];int dp(int y,int x){ int i,y2,x2; if(y==1 && x==1) return (D[y][x]=1); if(D[y][x]!=0) return D[y][x]; for(i=0;i<4;++i){ y2=y+dy[i]; x2=x+dx[i]; if(t[y2][x2]>t[y][x]) D[y][x]+=dp(y2, x2); } return D[y][x];}int main() { int x,y; scanf("%d%d", &M, &N); for(y=1;y<=M;++y) for(x=1;x<=N;++x) scanf("%d",&t[y][x]); printf("%d\n",dp(M,N)); return 0;}-끝-
'알고리즘 > 알고리즘 노트' 카테고리의 다른 글
| [자료구조]-[리스트]-문제 (0) | 2016.08.05 |
|---|---|
| [자료구조]-[스택]-문제 (0) | 2016.08.04 |
| [다이나믹]-문제2 (0) | 2016.07.30 |
| [다이나믹]-문제1 (0) | 2016.07.30 |
| [문자열] (0) | 2016.07.28 |