다이나믹 프로그래밍을 이용하는 문제 낮은 수의 동전부터 먼저 메모라이징해준 후 더 큰 수로 계속해서 메모링해 나아가서 

1원 2원 동전이 있을 경우 1 + 2, 2 + 1과 같이 반복되는 경우의 수를 없애 준다.



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
using namespace std;
int n, k;
int d[10001];
int coin[101];
int main()
{
    cin >> n >> k;
    for (int i = 0; i < n; ++i)
    {
        cin >> coin[i];
    }
    d[0] = 1;
    for (int i = 0; i < n; ++i)
    for (int j = 1; j <= k; ++j)
    {
        if (j - coin[i] >= 0)
            d[j] += d[j - coin[i]];
    }
    cout << d[k] << '\n';
    return 0;
}
cs


저작자표시 비영리 (새창열림)

'백준 온라인 저지' 카테고리의 다른 글

백준 1495: 기타리스트  (0) 2018.08.04
백준 2294: 동전2  (0) 2018.08.04
백준 10942: 팰린드롬?  (0) 2018.07.31
백준 1890: 점프  (0) 2018.07.31
백준 11048: 이동하기  (0) 2018.07.31


1 2 1 과 같이 대칭되는 숫자인지 판별하는 문제

다이나믹프로그램을 활용한다. d[i][j] 를 i번째 수 부터 j 번째가 팰린드롬인지 여부라고한다면 재귀로 d[i+ 1][j - 1]을 다이나믹으로 문제의 범위를 좁혀나가준다. 팰린드롬은 사실 n정도의 시간복잡도로 구해 줄 수 있지만 문제에서 엄청난 수의 문제를 구하라고 하기 때문에 문제의 정답을 기억해놓고 다시 써먹어야할 필요성이있다. 그래서 다이나믹을 활용하는 것이다.

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
#include <iostream>
#include <cstring>
using namespace std;
int a[2001];
int d[2001][2001];
int n, q;
 
int go(int start, int end)
{
    if (start == end)
    {
        return 1;
    }
    if (start + 1 == end){
        if (a[start] == a[end]){
            return 1;
        }
        else
            return 0;
    }
    if (d[start][end] != -1)
        return d[start][end];
    if (a[start] != a[end])
        return d[start][end] = 0;
    else return d[start][end] = go(start + 1, end - 1);
}
 
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    cin >> q;
    memset(d, -1, sizeof(d));
    int s, e;
    while (q != 0)
    {
        cin >> s >> e;
        cout << go(s ,e) << '\n';
        --q;
    }
    return 0;
}
cs


저작자표시 비영리 (새창열림)

'백준 온라인 저지' 카테고리의 다른 글

백준 2294: 동전2  (0) 2018.08.04
백준 2293: 동전 1  (0) 2018.08.04
백준 1890: 점프  (0) 2018.07.31
백준 11048: 이동하기  (0) 2018.07.31
백준 2263: 트리의 순회  (0) 2018.07.31

다이니믹 프로그래밍을 이용하는 문제 n,n에는 0 값이 들어있느니 자기자신을 계산하는 것을 방지하기 위해 continue 코드를 넣어준다.


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
#include <iostream>
#include <algorithm>
using namespace std;
int d[105][105];
int a[105][105];
int n;
 
int main()
{
    cin >> n;
    for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j)
    {
        cin >> a[i][j];
    }
    d[1][1] = 1;
    for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j)
    {
        if (a[i][j] == 0)
            continue;
        int jump = a[i][j];
        if (j + jump <= n)
            d[i][j + jump] += d[i][j];
        if (i + jump <= n)
            d[i + jump][j] += d[i][j];
    }
    cout << d[n][n] << endl;
    return 0;
}
cs


저작자표시 비영리 (새창열림)

'백준 온라인 저지' 카테고리의 다른 글

백준 2293: 동전 1  (0) 2018.08.04
백준 10942: 팰린드롬?  (0) 2018.07.31
백준 11048: 이동하기  (0) 2018.07.31
백준 2263: 트리의 순회  (0) 2018.07.31
백준 1931: 회의실 배정  (0) 2018.07.30

+ Recent posts

티스토리툴바