Week 1 - DP1

<180625>

### DP Basic ###

1) [11051] 이항계수2 : http://boj.kr/11051

combi(n, r) : nCr 을 구하는 함수. nCr = n-1Cr + n-1Cr-1

<소스코드>

#include <stdio.h>
 
const int MOD=10007;
 
int d[1001][1001];
 
int combi(int n, int r)
{
    int *ret = &d[n][r];
    if(r == 0 || r == n) return 1;
    if(*ret != -1) return *ret;
 
    return *ret = (combi(n-1, r-1)+combi(n-1, r))%MOD;
}
 
int main()
{
    int n, k;
    scanf("%d%d", &n, &k);
    for(int i=0; i<=n; i++)
        for(int j=0; j<=n; j++)
            d[i][j] = -1;
    printf("%d\n", combi(n, k));
    return 0;
}

2) [11055] 가장 큰 증가하는 부분 수열 : http://boj.kr/11055

d[i] : i ~ (n-1) 번째까지의 수열 중에서 가장 큰 증가하는 부분 수열의 합의 최대값

<소스코드>

#include <stdio.h>
 
int n;
int a[1001], d[1001];
 
int max(int a, int b)
{
    return a > b ? a : b;
}
 
int lis(int s)
{
    int *ret = &d[s];
    if(s == n-1) return a[s];
    if(*ret) return *ret;
 
    *ret = a[s];
    for(int i=s+1; i<n; i++) {
        if(a[s] < a[i])
            *ret = max(*ret, a[s]+lis(i));
    }
    return *ret;
}
 
int main()
{
    int ans=0;
    scanf("%d", &n);
 
    for(int i=0; i<n; i++)
        scanf("%d", a+i);
 
    for(int i=0; i<n; i++)
        ans = max(ans, lis(i));
    printf("%d\n", ans); 
    return 0;
}
 

3) [11048] 이동하기 : http://boj.kr/11048

d[i][j] : (i,j) 에서 이동해서 가져올 수 있는 사탕 갯수의 최대값

<소스코드>

#include <stdio.h>
 
int g[1001][1001];
int d[1001][1001];
 
int max(int a, int b)
{
    return a > b ? a : b;
}
 
int move(int r, int c)
{
    int *ret = &d[r][c];
    if(r <= 0 || c <= 0) return 0;
    if(*ret != -1) return *ret;
    
    *ret = move(r-1, c)+g[r][c];
    return *ret = max(*ret, move(r, c-1)+g[r][c]);
}
 
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
 
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            scanf("%d", &g[i][j]);
            d[i][j] = -1;
        }
    }
 
    printf("%d\n", move(n, m));
    return 0;
}
 

4) [11066] 파일합치기 : http://boj.kr/11066

d[i][j] : i~j번째 까지의 파일을 합치는 데 드는 최소 비용

<소스코드>

#include <stdio.h>
 
int n, a[501];
int d[501][501];
int pSum[501];
 
int min(int a, int b)
{
    return a < b ? a : b;
}
 
int file(int s, int e)
{
    int *ret = &d[s][e];
    if(s == e) return 0;
    if(*ret != -1) return *ret;
 
    *ret = 0x7fffffff;
    for(int i=s; i<e; i++) 
        *ret = min(*ret, file(s, i)+file(i+1, e)); 
    return *ret = *ret + (pSum[e]-pSum[s-1]);
}
 
int main()
{
    int tc;
    scanf("%d", &tc);
 
    while(tc--) {
        scanf("%d", &n);
        for(int i=1; i<=n; i++)
            pSum[i] = 0;
        for(int i=1; i<=n; i++) {
            scanf("%d", a+i);
            pSum[i] += (pSum[i-1]+a[i]);
 
            for(int j=1; j<=n; j++) 
                d[i][j] = -1;
        }
        printf("%d\n", file(1, n));
    }
 
    return 0;
}
 

>> 누적합을 누적해나가야 한다.

>> pSum 을 초기화 안해서 뻣질 많이 함...ㅜㅜ

<180629>

1) [2410] 2의 멱수의 합 : http://boj.kr/2410

2) [2228] 구간 나누기 : http://boj.kr/2228