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/source/6343472


사이클이 몇개인지 찾는 문제입니다.!


인풋에서 1차원 배열에 다음 노드가 뭔지 저장 하고!

방문체크 하면서 들어갔던 곳으로 또가면 싸이클이 형성이되겠죠!


여기서 싸이클 종류가 두개가 생기죠!!

1. 순열 싸이클

2. 구냥 싸이클


1번은 문제에서 제시한거처럼 시작점으로 다시 돌아오는 사이클을 '순열 사이클'이라고 하는거같아요!

2번은 시작점을 제외한 노드로 다시 방문하는 경우 순열 사이클이 아니겠지요~~~


코드 보시면 이해가실거에욥!!


코드입니당.

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
#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);
 
int nextNode[1001];
bool visit[1001];
 
bool isCycle(int start, int now) {
    visit[now] = 1;
 
    if (nextNode[now] == start) return 1; //다음 노드가 시작점이면 싸이클이 맞으므로 리턴
    else if (visit[nextNode[now]]) return 0; // 시작점이 아닌데 방문했던 곳을 방문한다?? 온전한 순열 사이클이 아니죵
    else return isCycle(start, nextNode[now]); // 방문안했으면 무작정 들어가기!!!!!!!!!!!
}
 
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
 
    int t;
    cin >> t;
 
    while (t--) {
        memset(visit, 0, sizeof(visit));
        int n;
        cin >> n;
 
        for (int i = 1; i <= n; i++) {
            cin >> nextNode[i];
        }
 
        int ret = 0;
        for (int i = 1; i <= n; i++) {
            if (visit[i]) continue;
            ret += isCycle(i, i);
        }
        cout << ret << '\n';
    }
    return 0;
}
cs


저작자표시

'알고리즘 > 탐색' 카테고리의 다른 글

[2667] 단지번호붙이기  (0) 2017.09.15
[10216] Count Circle Groups  (0) 2017.08.10
[10974] 모든 순열  (2) 2017.07.27
[1058] 친구  (0) 2017.07.20
[1941] 소문난 칠공주  (1) 2017.07.01

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


음..

next_permutation??이라는 함수가 있습니다.

알고리즘 헤더에 있는 함수인데..

이거 쓰면 엄청 쉽게 풀 수 있는데!!!!!!!!!!


기초가 튼튼해야합니다!


dfs로 해봅시다!!!!!!!!!!!!!!!!!!!!!!

그냥 배열을 n의 최대값만큼 만들어서

방문체크하면서 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
#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);
 
bool visit[10];
int output[10];
 
void f(int num, int d, int n) {
    output[d] = num;
 
    if (d == n) {
        for (int i = 1; i <= n; i++) cout << output[i] << ' ';
        cout << '\n';
        return;
    }
 
 
    for (int i = 1; i <= n; i++) {
        if (visit[i]) continue;
        visit[i] = 1;
        f(i, d + 1, n);
        visit[i] = 0;
    }
}
 
int main() {
    int n;
    cin >> n;
 
    for (int i = 1; i <= n; i++) {
        visit[i] = 1;
        f(i, 1, n);
        visit[i] = 0;
    }
 
    return 0;
}
cs


저작자표시

'알고리즘 > 탐색' 카테고리의 다른 글

[10216] Count Circle Groups  (0) 2017.08.10
[10451] 순열 사이클  (0) 2017.07.27
[1058] 친구  (0) 2017.07.20
[1941] 소문난 칠공주  (1) 2017.07.01
[2146] 다리 만들기  (2) 2017.05.23

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/10986


분류가... https://www.acmicpc.net/problem/tag/Prefix%20Sum


prefix sum??이라고 되어있네요..뭔지 잘모르겠습니당.....


이 문제는 


(a + b) % MOD = (a % MOD + b % MOD) % MOD
라는 것을 이용해야합니다.


a1 + a2 + a3 + ... + an = Sn

이라고 했을 때


aj + a(j+1) + a(j + 2) + ... ai = Si - S(j-1)


입니다.


예제의

5 3
1 2 3 1 2


라고 인풋이 들어오면


2 3 1을 더해도 3으로 나눴을때 나머지가 0이되겠죠??


이것을 어떻게 찾냐???

하면


1 2 3 1 을 다더하면 7이 나오겟죠??


근데 인덱스 0까지의 합은 1입니다.


그렇다면 

인덱스 1~3은 S3 - S0입니다.


S0의 나머지는 1

S3의 나머지 또한 1이죠


그렇다하면 나머지 두개가 같은 이 S3 와 S0을 뺀다면

나머지가 0이됩니다.

즉 이 둘을 뻇을 때 나머지가 0이라는 말입니다.


데이터를 받을 때마다 연속적으로 합을 구해서 mod값으로 나누고 나눈 나머지값들을 각각

카운트합니다.


그리고 m미만의 각 개수에 대해서 n(해당 모드의 개수)C2를 해주면됩니다.(n개 중에 2개를 고르는 방법)


주의할 점은 나머지가 0인경우 nC2 + 자기자신도 이미 나누어지기 때문에 자기자신의 개수까지 더해야한다는 점입니다.


코드입니다.

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>
#include <vector>
 
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 main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int n, m;
    cin >> n >> m;
 
    ll sum = 0;
    ll c[1000] = { 0, };
 
    //인풋받으면서 sum에다가 인풋받은값을 계속더해줌
    //그리고 그 합에 대해서 mod를 나눠서 c라는 배열에 카운팅해줌.
    while (n--) {
        int a;
        cin >> a;
        sum += a;
        c[sum % m]++;
    }
 
    ll ret = c[0];//0은 그자체로 이미 나머지가 0이기때문에
    for (int i = 0; i < m; i++) ret += (c[i] * (c[i] - 1)) / 2;//nC2
 
    cout << ret;
 
    return 0;
}
 
cs


저작자표시

'알고리즘 > 구현' 카테고리의 다른 글

[1913] 달팽이  (0) 2017.07.27
[14649] 문홍안  (0) 2017.07.27
[3474] 교수가 된 현우  (0) 2017.07.13
[5527] 전구 장식  (0) 2017.07.05
[14499] 주사위 굴리기  (0) 2017.04.16

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/14588


어떠한 선분과 선분의 관계를

2차원 배열로 만들어서 표현할 수 있겠다고 생각했습니다.


그래서 우선 거리가 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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <iostream>
#include <string.h>
#include <queue>
#include <algorithm>
 
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 dist[300][300];
vector<pii> v;
 
bool f(int a, int b) {
    if (v[a].second < v[b].first || v[b].second < v[a].first) return 0;
    return 1;
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
 
    int n;
    cin >> n;
 
    for (int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        v.push_back(mp(a, b));
    }
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i == j) continue;
            else dist[i][j] = INF;
        }
    }
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i == j) continue;
            if (f(i, j)) {
                dist[i][j] = 1;
                dist[j][i] = 1;
            }
        }
    }
 
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (dist[i][j] > dist[i][k] + dist[k][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
 
    int q;
    cin >> q;
    for (int i = 0; i < q; i++) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        cout << (dist[a][b] == INF ? -1 : dist[a][b]) << '\n';
    }
 
    return 0;
}
cs


저작자표시

'알고리즘 > 최단 거리' 카테고리의 다른 글

[1686] 복날  (0) 2017.07.12
[1507] 궁금한 민호  (0) 2017.07.08

+ Recent posts

티스토리툴바