다이나믹을 사용하면 되는 문제 경우의 수가 오지게 많아서 long long 을 써줘야 한다. int 썻다가 피를 봤다.. 원리는 어렵지 않다. 점화식을 세우면 되는데

d[i번째 수를 사용][현재 수] 가 경우의 수를 나타낸다고 했을 때 입력받은 a배열에서 해당 만큼 빼주고 더해주면 된다. 


신기한 건 나는 답을 못찾겠을 때 구글에 백준 문제 번호를 검색하는데 내 코딩과 비슷한 사람이 보인다..


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
#include <iostream>
using namespace std;
int n;
long long d[103][21];
int a[103];
 
int main()
{
    cin >> n;
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    d[0][a[0]] = 1;
    for (int i = 1;i <= n - 2; ++i)
    for (int j = 0; j <= 20; ++j)
    {
        if (d[i - 1][j])
        {
            if (j - a[i] >= 0)
                d[i][j - a[i]] += d[i - 1][j];
            if (j + a[i] <= 20)
                d[i][j + a[i]] += d[i - 1][j];
        }        
    }
    long long ans = d[n - 2][a[n - 1]];
    cout << ans << endl;
    return 0;
}
cs


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

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

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

다이나믹 프로그램을 사용한다. 재귀적 방법을 사용했다. 연주가능하면 1 불가능하면 0 방식을 사용해 시작점부터 마치 분할 정복 하듯이 내려간다. 하지만 분할 정복은 아니다 왜냐하면 만약 같은 볼륨 값을 가르키는 지점에 여러 전 곡에서 도달했을 때 한 가지 경우만 세면 되기 때문이다. 


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 <iostream>
using namespace std;
int n, s, m;
int d[105][1005];
int v[105];
void go(int cur_n, int cur_vol)
{
    if (d[cur_n][cur_vol] != 0)
        return;
    d[cur_n][cur_vol] = 1;
    if (cur_n == n)
        return;
    if (cur_vol - v[cur_n + 1] >= 0)
    {
        go(cur_n + 1, cur_vol - v[cur_n + 1]);
    }
        
    if (cur_vol + v[cur_n + 1] <= m)
    {    
        go(cur_n + 1, cur_vol + v[cur_n + 1]);
    }
    return;
}
 
int main()
{
    cin >> n >> s >> m;
 
    for (int i = 1;i <= n; ++i)
        cin >> v[i];
    go(0, s);
    int ans = -1;
    for (int i = 0;i <= m; ++i)
    if (d[n][i] == 1)
        ans = i;
    cout << ans << endl;
    return 0;
}
cs


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

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

백준 5557: 1학년  (0) 2018.08.04
백준 2294: 동전2  (0) 2018.08.04
백준 2293: 동전 1  (0) 2018.08.04
백준 10942: 팰린드롬?  (0) 2018.07.31
백준 1890: 점프  (0) 2018.07.31

다이나믹 프로그래밍을 사용하는 문제 d를 0부터 끝까지 순회하므로 만약 d[i]번째에 도달하는 경로가 없을 경우 이를 계산하지 않도록 유의하면서 if문을 짜줘야한다. j원에서 동전 값을 뺀 것이 0보다 크고 동시에  d[j - coin[i]] 또한 -1 (배열을 -1로 값을 설정했다.)이 아니어야 이전에 값이 메모라이징 됬었다는 것이고 처음 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
#include <iostream>
#include <algorithm>
using namespace std;
int n, k;
int coin[106];
int d[10006];
 
int main()
{
    cin >> n >> k;
    for (int i = 0; i < n; ++i)
        cin >> coin[i];
    for (int i = 0; i < 10006; ++i)
        d[i] = -1;
    d[0] = 0;
    for (int i = 0; i < n; ++i)
    for (int j = 1; j <= k; ++j)
    {
        if (j - coin[i] >= 0 && d[j - coin[i]] != -1){
            if (d[j] == -1)
                d[j] = d[j - coin[i]] + 1;
            else
                d[j] = min(d[j], d[j - coin[i]] + 1);
        }
    }
    cout << d[k] << '\n';
    return 0;
}
cs


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

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

백준 5557: 1학년  (0) 2018.08.04
백준 1495: 기타리스트  (0) 2018.08.04
백준 2293: 동전 1  (0) 2018.08.04
백준 10942: 팰린드롬?  (0) 2018.07.31
백준 1890: 점프  (0) 2018.07.31

+ Recent posts

티스토리툴바