How We Coding

Week 1 - DP1

Tutoring/PS2018. 6. 26. 15:43

<180625>


### DP Basic ###


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


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


<소스코드>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#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;
}
cs



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


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


<소스코드>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#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;
}
 
cs



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


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


<소스코드>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#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;
}
 
cs




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


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


<소스코드>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#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;
}
 
cs


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

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



<180629>


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



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


'Tutoring > PS' 카테고리의 다른 글

Week 7 - DFS+BFS  (0) 2018.04.07
Week 6 - BFS (숨박꼭질)  (0) 2018.03.30
Week 5 - BFS  (0) 2018.03.24
Week 4 - BFS  (0) 2018.03.11
Week3 - DFS  (0) 2018.03.07

[11985] 오렌지 출하

BOJ/DP2018. 6. 21. 01:18

### DP ###


[11985] 오렌지 출하 : http://boj.kr/11985


<소스코드>


d[i] : i번째 오랜지부터 포장했을 때, 비용의 최소값.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <stdio.h>
 
int a[20001];
long long d[21001];
int n, m, k;
 
long long min(long long a, long long b)
{
    return a < b ? a : b;
}
 
long long orange(int s, int e)
{
    long long *ret = &d[s];
    int size, big=0, small=0x7fffffff;
    long long box;
 
    if(s >= e) return 0;
    if(*ret != -1) return *ret;
 
    *ret = 0x7fffffffffffffff;
    size = m < e-s+1 ? m : e-s+1;
    for(int i=0; i<size; i++) {
        if(big < a[s+i]) big = a[s+i];
        if(small > a[s+i]) small = a[s+i];
        box = 1LL*(i+1)*(big-small) + k;
        *ret = min(*ret, box+orange(s+i+1, e));
    }
    return *ret;
}
 
int main()
{
    scanf("%d%d%d", &n, &m, &k);
 
    for(int i=0; i<n; i++) {
        scanf("%d", a+i);
        d[i] = -1;
    }
 
    printf("%lld\n", orange(0, n));
    return 0;
}
 
cs


>> 시간복잡도 : O(NM)

'BOJ > DP' 카테고리의 다른 글

[9177] 단어 섞기  (0) 2018.05.22
[2602] 돌다리 건너기  (0) 2018.05.17
[9252] LCS2  (0) 2018.04.22
[9251] LCS  (0) 2018.04.21
[14002] 가장 긴 증가하는 부분 수열 4  (0) 2018.04.18

[3124] 최소 스패닝 트리

PS/SW Expert Academy2018. 6. 20. 21:11

### SW Expert Academy - D4 ###


[3124] 최소 스패닝 트리 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV_mSnmKUckDFAWb&categoryId=AV_mSnmKUckDFAWb&categoryType=CODE


<소스코드>


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
 
struct P { int f, t, w; };
 
int p[100001];
 
bool cmp(P a, P b)
{
    return a.w < b.w;
}
 
int find(int x)
{
    return p[x] = p[x] == x ? x : find(p[x]);
}
 
bool Union(int a, int b)
{
    a = find(a);
    b = find(b);
    if(a == b) return 0;
    p[a] = b;
    return 1;
}
 
int main()
{
    int T;
    scanf("%d", &T);
 
    for(int tc=1; tc<=T; tc++) {
        int v, e;
        scanf("%d%d", &v, &e);
 
        for(int i=1; i<=v; i++)
            p[i] = i;
 
        vector<P> g;
        for(int i=0; i<e; i++) {
            int a, b, c;
            scanf("%d%d%d", &a, &b, &c);
            g.push_back((P){a, b, c});
        }
        
        sort(g.begin(), g.end(), cmp);
 
        long long ans=0LL;
        for(int i=0; i<e; i++) 
            if(Union(g[i].f, g[i].t)) 
                ans += g[i].w;
        printf("#%d %lld\n", tc, ans);
    }
    return 0;
}
 
cs


>> Union-Find 를 이용한 크루스칼 알고리즘 사용.

>> ans 값은 int 범위를 벗어남에 주의.


'PS > SW Expert Academy' 카테고리의 다른 글

[1486] 장훈이의 높은 선반  (0) 2018.06.20
[4408] 자기방으로 돌아가기  (0) 2018.06.10

티스토리툴바