https://www.acmicpc.net/problem/1365


LIS 문제입니다.

꼬이지 않으려면 내가 연결한 전봇대 보다 번호가 더 큰 전봇대만 선택해야하기 때문입니다.

N^2의 방법으로 해결하려고 했으나,  N이 너무 큽니다.


NlogN으로 해결하는 Lower Bound LIS로 해결해야합니다.

저도 처음해봤는데..


우선 로워바운드는 해당 숫자 이상의 수 중에서 가장 가까운 인덱스를 리턴하는 함수입니다.

(정렬이 되어있을 떄만 가능합니다. 이분 탐색을 응용한 것이기 떄문입니다.)


a배열은 입력들어오는 배열이고

b배열은 정렬된 수가 들어가 있는 배열입니다.

주의할 점은 b배열이 lis의 부분수열이 들어가있는 배열이 아니라는 점입니다.


로워 바운드는 자기보다 작거나 같은 경우 b배열에서 수행해서 자기의 위치를 찾아서 대입합니다.


예를 들어 10 20 30 1 2 3 4 5

라는 수열이 있으면


b배열에 10 20 30 이렇게 들어갈 것입니다.

허나 1을 만나면 10 20 30 이 들어있는 수열에서

로워바운드를 하여 자기 이상의 수 중 가장 인덱스를 찾겠죠.

네 value:10, idx:0 입니다.

그러면 b 배열은 1 20 30으로 바뀌게 됩니다.


또 2를 만나면 자기보다 큰 수를 찾겠죠. 네 20입니다.

1 2 30 으로 바뀌게 됩니다.


3을 만나면

1 2 3으로 바뀌겠죠.

4와 5는 b배열의 3보다 크므로 그냥 삽입하면 됩니다.


b배열은 1 2 3 4 5가 완성이 됩니다.

결국 lis값은 5가 되겠죠.


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
#include <stdio.h>
 
using namespace std;
int a[(int)1e5];
int b[(int)1e5];
 
int lower_bound(int s, int e, int value) {
    
    while (s <= e) {
        int mid = (s + e) / 2;
 
        if (b[mid] >= value) e = mid - 1;
        else s = mid + 1;
    }
 
    return s;
}
 
int main() {
    int n;
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
        
    int size = 1;
    b[0] = a[0];
    
    for (int i = 1; i < n; i++) {
        if (b[size - 1] < a[i]) {
            b[size] = a[i];
            size++;
            continue;
        }
 
        b[lower_bound(0, size - 1, a[i])] = a[i];
    }
    
    printf("%d", n - size);
 
    return 0;
}
cs


저작자표시

'알고리즘 > 다이나믹 프로그래밍(DP)' 카테고리의 다른 글

[1890] 점프  (0) 2017.09.15
[2565] 전깃줄  (0) 2017.09.07
[2688] 줄어들지 않아  (0) 2017.07.27
[12026] BOJ 거리  (0) 2017.07.24
[1563] 개근상  (0) 2017.07.24

https://www.acmicpc.net/problem/1890


이 문제는 어렵지 않았습니다.

dp라고 알 수 있는 부분은 이 문제가 경우의 수이고, 정답이 2^63이라면 DP를 제외하고는 시간안에 풀 수 없습니다.


dp라는 것만 안다면 어렵지 않은 문제입니다.


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
#include <iostream>
 
using namespace std;
 
typedef long long ll;
 
int dx[] = { 1, 0 };
int dy[] = { 0, 1 };
 
int map[100][100];
ll dp[100][100];
 
int n;
 
ll f(int x, int y) {
    if (x == n - 1 && y == n - 1) {
        return 1;
    }
 
    ll &ret = dp[x][y];
    if (ret != -1) return ret;
    ret = 0;
 
    for (int i = 0; i < 2; i++) {
        int nx = x + dx[i] * map[x][y];
        int ny = y + dy[i] * map[x][y];
        if (nx >= n || ny >= n) continue;
 
        ret += f(nx, ny);
    }
 
    return ret;
}
 
int main() {
    cin >> n;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> map[i][j];
            dp[i][j] = -1;
        }
    }
 
    cout << f(0, 0);
 
    return 0;
}
cs


저작자표시

'알고리즘 > 다이나믹 프로그래밍(DP)' 카테고리의 다른 글

[1365] 꼬인 전깃줄  (0) 2017.09.16
[2565] 전깃줄  (0) 2017.09.07
[2688] 줄어들지 않아  (0) 2017.07.27
[12026] BOJ 거리  (0) 2017.07.24
[1563] 개근상  (0) 2017.07.24

https://www.acmicpc.net/problem/2565


LIS문제라는 것을 눈치채지 못한 저는 바보입니다.


LIS입니다..


전형적인 DP문제죠...


dp[n] : 인덱스 n까지의 최대 연결 수


라고 정의하면 됩니다.


이렇게 하면 N^2의 시간복잡도로 해결할 수 있습니다.


관련 문제..

https://www.acmicpc.net/problem/1965

https://www.acmicpc.net/problem/2352


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 <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <string.h>
#include <stack>
#include <cstdio>
 
#define mp make_pair
#define MOD 1000000007
#define INF 0x7fffffff
#define MAX_SIZE (int)1e5
 
using namespace std;
//ios::sync_with_stdio(false); cin.tie(0);
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef vector<pll> vll;
typedef vector<bool> vb;
 
int edge[501];
int dp[501];
 
int main() {
    int n;
    cin >> n;
 
    for (int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
 
        edge[a] = b;
    }
 
    int ret = 0;
 
    for (int i = 1; i <= 500; i++) {
        if (edge[i] == 0) continue;
 
        dp[i] = 1;
 
        for (int j = 1; j < i; j++) {
            if (edge[j] < edge[i]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
 
        ret = max(ret, dp[i]);
    }
    
    cout << n - ret;
 
    return 0;
}
cs


저작자표시

'알고리즘 > 다이나믹 프로그래밍(DP)' 카테고리의 다른 글

[1365] 꼬인 전깃줄  (0) 2017.09.16
[1890] 점프  (0) 2017.09.15
[2688] 줄어들지 않아  (0) 2017.07.27
[12026] BOJ 거리  (0) 2017.07.24
[1563] 개근상  (0) 2017.07.24

https://www.acmicpc.net/problem/2688


2차원 DP로 정의하시면 쉽게 해결할 수 있습니다.


dp[자리수][현재 수]라고 정의하면 되겠습니당.


그리고 dfs안에서 포문은 자기 자신과 같거나 큰수로 이동하면 되겠습니다!!!!!!!!!!!!


코드입니당!~_~

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
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <string.h>
using namespace std;
 
#define ll long long
#define MOD (ll)1e15
#define MAX_SIZE (int)1e5
#define mp make_pair
#define INF 987654321
#define pii pair<int, int>
//ios::sync_with_stdio(false); cin.tie(0);
 
ll dp[65][10];
int n;
 
ll f(int d, int now) {
    if (d == n) return 1;
 
    ll &ret = dp[d][now];
    if (ret != -1) return ret;
    ret = 0;
 
    for (int i = now; i < 10; i++) {
        ret += f(d + 1, i);
    }
 
    return ret;
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
 
    int t;
    cin >> t;
 
    while (t--) {
        memset(dp, -1, sizeof(dp));
 
        cin >> n;
 
        ll ret = 0;
        for (int i = 0; i < 10; i++) ret += f(1, i);
 
        cout << ret << '\n';
    }
    return 0;
}
cs


저작자표시

'알고리즘 > 다이나믹 프로그래밍(DP)' 카테고리의 다른 글

[1890] 점프  (0) 2017.09.15
[2565] 전깃줄  (0) 2017.09.07
[12026] BOJ 거리  (0) 2017.07.24
[1563] 개근상  (0) 2017.07.24
[2225] 합 분해  (0) 2017.07.24

https://www.acmicpc.net/problem/12026


전형적인 DP문제네요.

1차원 DP이구요

정의는 n까지가는데 최소 비용이라고 정의하면 되겠습니다.


메모이제이션을 하면서 재귀를 돌렸습니다.


문제 풀 떄 꿀팁은 인풋을 받을 때가 중요합니다.

B = 0

O = 1

J = 2

로 배열에 저장했습니다.


그래서 B다음에 O로 갈 땐 (arr[현재 위치] + 1) % 3 == arr[다음 위치] 이 조건이 성립하는 곳으로 이동하시면 됩니다.


코드입니다.

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
#include <iostream>
#include <vector>
 
#include <string.h>
using namespace std;
 
#define ll long long
#define MOD (ll)1e15
#define MAX_SIZE (int)1e5
#define mp make_pair
#define INF 987654321
#define pii pair<int, int>
//ios::sync_with_stdio(false); cin.tie(0);
 
int street[1000];
 
int dp[1000];
int n;
 
int min(int a, int b) {
    return a < b ? a : b;
}
 
int dfs(int pos) {
    if (pos == n - 1) return 0;
 
    int &ret = dp[pos];
    if (ret != -1) return ret;
    ret = INF;
    
    for (int i = pos + 1; i < n; i++) if(street[i] == (street[pos] + 1) % 3) ret = min(ret, dfs(i) + (i - pos) * (i - pos));
 
    return ret;
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> n;
    
    for (int i = 0; i < n; i++) {
        char c;
        cin >> c;
        if (c == 'B') street[i] = 0;
        else if (c == 'O') street[i] = 1;
        else street[i] = 2;
    }
 
    memset(dp, -1, sizeof(dp));
 
    int ret = dfs(0);
    cout << (ret == INF ? -1 : ret);
 
    return 0;
}
 
cs


저작자표시

'알고리즘 > 다이나믹 프로그래밍(DP)' 카테고리의 다른 글

[2565] 전깃줄  (0) 2017.09.07
[2688] 줄어들지 않아  (0) 2017.07.27
[1563] 개근상  (0) 2017.07.24
[2225] 합 분해  (0) 2017.07.24
[2158] 동전 교환  (0) 2017.07.09

https://www.acmicpc.net/problem/1563



이 문제는


두가지로 dp를 정의해보았습니다.


첫번째로 풀 때는

dp[날짜][지각 수][현재 날짜의 전 전에 결석했는지][현재 날짜의 전 날에 결석했는지]

라고 처음에 정의했습니다.


근데 이 방법보다 간단하게 정의할 수 있습니다.

3차원 dp인데요


dp[날짜][지각 수][연속으로 결석한 수] 라고 정의할 수 있습니다.

연속으로 결석한 수 라고 정의한 이유는


결석한 수가 연속이지 않으면 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
39
#include <iostream>
#include <string.h>
using namespace std;
 
#define ll long long
#define MOD (ll)1e6
#define MAX_SIZE (int)1e5
#define mp make_pair
#define INF 987654321
#define pii pair<int, int>
//ios::sync_with_stdio(false); cin.tie(0);
int dp[1001][2][3];
int n;
 
int f(int date, int late, int absence) {
    if (late == 2) return 0;
    else if (absence == 3) return 0;
    
    if (date == n) return 1;
        
    int &ret = dp[date][late][absence];
    if (ret != -1) return ret;
    ret = 0;
 
    ret += f(date + 1, late + 1, 0) + f(date + 1, late, absence + 1) + f(date + 1, late, 0);
 
    return ret % MOD;
}
 
 
int main() {
    cin >> n;
 
    memset(dp, -1, sizeof(dp));
 
    cout << f(0, 0, 0);
    return 0;
}
 
cs

이 아래는 첫번째 방법입니다.

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
#include <iostream>
#include <string.h>
using namespace std;
 
#define ll long long
#define MOD (ll)1e6
#define MAX_SIZE (int)1e5
#define mp make_pair
#define INF 987654321
#define pii pair<int, int>
//ios::sync_with_stdio(false); cin.tie(0);
int dp[1001][3][2][2];//date/late/1 2 3 
int n;
 
int f(int date, int late, int pprev, int prev) {
    if (date == n) return 1;
    int &ret = dp[date][late][pprev][prev];
    if (ret != -1) return ret;
    ret = 0;
 
    if (pprev && prev) {
        if (late < 1) ret += f(date + 1, late + 1, prev, 0) % MOD;
        ret += f(date + 1, late, prev, 0) % MOD;
    }
    else {
        if (late < 1) ret += f(date + 1, late + 1, prev, 0) % MOD;
        ret += f(date + 1, late, prev, 1) % MOD;
        ret += f(date + 1, late, prev, 0) % MOD;
    }
 
    return ret % MOD;
}
 
 
int main() {
    cin >> n;
 
    memset(dp, -1, sizeof(dp));
 
    cout << f(0, 0, 0, 0);
    return 0;
}
 
cs


저작자표시

'알고리즘 > 다이나믹 프로그래밍(DP)' 카테고리의 다른 글

[2688] 줄어들지 않아  (0) 2017.07.27
[12026] BOJ 거리  (0) 2017.07.24
[2225] 합 분해  (0) 2017.07.24
[2158] 동전 교환  (0) 2017.07.09
[1102] 발전소  (0) 2017.07.08

https://www.acmicpc.net/problem/2225


이 문제는 2차원 dp로 간단하게 해결할 수 있습니다.

dp[sum][수를 쓴 수]라고 정의를 했습니다.


저는 dfs를 이용해서 메모이제이션했는데요

만약 sum이 N을 초과하면 0을 리턴합니다 더 들어갈 필요도 없기 때문입니다.

만약 해당 깊이(수를 쓴 수와 같음)가 되었는데 내가 원하는 N이 아니라면 0을 리턴하고 맞으면 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
39
40
41
42
43
44
#include <iostream>
#include <string.h>
using namespace std;
 
#define ll long long
#define MOD (int)1e9
#define MAX_SIZE (int)1e5
#define mp make_pair
#define INF 987654321
#define pii pair<int, int>
//ios::sync_with_stdio(false); cin.tie(0);
int dp[201][201];
int n, k;
 
int f(int sum, int d) {
    if (sum > n) return 0;
    if (d == k) {
        if (sum == n) return 1;
        else return 0;
    }
 
    int &ret = dp[sum][d];
    if (ret != -1) return ret;
 
    ret = 0;
 
    for (int i = 0; i <= n; i++) {
        ret += f(sum + i, d + 1);
        ret %= MOD;
    }
 
    return ret;
}
 
int main() {
    cin >> n >> k;
 
    memset(dp, -1, sizeof(dp));
 
    cout << f(0, 0);
 
    return 0;
}
 
cs


저작자표시

'알고리즘 > 다이나믹 프로그래밍(DP)' 카테고리의 다른 글

[12026] BOJ 거리  (0) 2017.07.24
[1563] 개근상  (0) 2017.07.24
[2158] 동전 교환  (0) 2017.07.09
[1102] 발전소  (0) 2017.07.08
[2698] 인접한 비트의 개수  (0) 2017.07.04

https://www.acmicpc.net/problem/1398


처음에 그리디로 접근했는데.. 생각해보니 잘못된 접근이었습니다.

1, 10, 25, 100, 1000, 2500, ... 이렇게 코인이 진행되는데

이 수들이 서로 배수라면 그리디로 해결해도 괜찮지만

10에서 25, 1000에서 2500 ...... 이런식으로 배수가 아닌 경우가 존재합니다.


그렇기 떄문에 그리디는 잘못된 방법입니다.


다음에 생각한 방법이 재귀를 이용하여 완전탐색으로 해봤습니다.

결과는 잘나오나 어떤 부분이 틀린지 잘모르겠습니다.


그래서 블로그를 찾다 보니 푸는 방법이 굉장히 신기했습니다.


1, 10, 25

100, 1000, 2500

10000, 100000, 250000

.

.

.

한단계 단계가 100으로 나눌 떄 같아지는 것을 이용한 풀이입니다.


dp를 이용해서

0~99까지 최소 코인 수를 구합니다.


그 후에 입력 받은 n을 100씩 나누면서 더해주면 답이 되는 문제입니다..

어떻게 생각하지 ..ㅡ.ㅡ..... 천재들...


아래는 풀 코드입니다.

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
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <string.h>
#include <queue>
#include <iostream>
#include <algorithm>
#include <vector>
#include <functional>
#include <stack>
#include <string>
 
#define ll long long
#define INF 0x7fffffff
#define MOD 1000000
#define MAX_SIZE 101
#define mp make_pair
#define pii pair<int, int>
using namespace std;
 
int main() {
    int coin[] = { 1, 10, 25 };
    int dp[100] = { 0, };
 
    for (int i = 1; i < 100; i++) {
        dp[i] = INF;
        for (int j = 0; j < 3; j++) {
            if (i - coin[j] >= 0) {
                dp[i] = min(dp[i], dp[i - coin[j]] + 1);
            }
        }
    }
 
    int t;
    cin >> t;
 
    while (t--) {
        ll n;
        cin >> n;
 
        ll ret = 0;
 
        while (n) {
            int nMod100 = n % 100;
 
            ret += dp[nMod100];
            n /= 100;
        }
 
        cout << ret << '\n';
    }
 
    return 0;
}
 
cs


'알고리즘 > 다이나믹 프로그래밍(DP)' 카테고리의 다른 글

[1563] 개근상  (0) 2017.07.24
[2225] 합 분해  (0) 2017.07.24
[1102] 발전소  (0) 2017.07.08
[2698] 인접한 비트의 개수  (0) 2017.07.04
[1029] 그림 교환  (0) 2017.06.27

+ Recent posts

티스토리툴바