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

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


(친구)와 (친구의 친구)의 최대치를 출력하는 문제입니다.

간단하게 생각했고 bfs를 이용하여 너비 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
52
53
54
55
56
57
58
59
60
61
62
63
#include <iostream>
#include <string.h>
#include <queue>
 
using namespace std;
 
#define ll long long
#define MOD (ll)1e15
#define MAX_SIZE 500000
//ios::sync_with_stdio(false); cin.tie(0);
 
char map[55][55];
bool visit[55];
int n;
 
int bfs(int vertex) {
    memset(visit, 0, sizeof(visit));
 
    queue<pair<int, int> > q;
    
    q.push(make_pair(vertex, 0));
    visit[vertex] = 1;
 
    while (!q.empty()) {
        int now = q.front().first;
        int breath = q.front().second;
        q.pop();
 
        if (breath == 2) break; //친구의 친구가 되면 탈출
 
        for (int i = 0; i < n; i++) {
            if (map[now][i] == 'Y' && !visit[i]) {
                visit[i] = 1;
                q.push(make_pair(i, breath + 1));
            }
        }
    }
 
    int ret = 0;
    for (int i = 0; i < n; i++) ret += visit[i];
 
    return ret - 1; // 자기 자신은 제외
}
 
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> n;
 
    //인풋
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> map[i][j];
        }
    }
 
    int ret = 0;
    for (int i = 0; i < n; i++) ret = max(ret, bfs(i));
 
    cout << ret;
 
    return 0;
}
cs


저작자표시

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

[10451] 순열 사이클  (0) 2017.07.27
[10974] 모든 순열  (2) 2017.07.27
[1941] 소문난 칠공주  (1) 2017.07.01
[2146] 다리 만들기  (2) 2017.05.23
[14503] 로봇 청소기  (2) 2017.04.18

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


음..

정수론 문제입니다.

0의 개수를 체크하라...


숫자의 뒤에 0이 붙으려면 소인수 분해를 했을 때

2와 5가 있어야합니다.


코드 공개합니다!

(사실 2를 안세고 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 <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 987654321
#define MOD 10000
#define MAX_SIZE 751
#define mp make_pair
#define pii pair<int, int>
//ios::sync_with_stdio(false); cin.tie(0);
using namespace std;
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
 
        ll cnt2 = 0, cnt5 = 0;
 
        for (int i = 2; i <= n; i *= 2) {
            cnt2 += n / i;
        }
 
        for (int i = 5; i <= n; i *= 5) {
            cnt5 += n / i;
        }
 
        printf("%lld\n", min(cnt2, cnt5));
    }
    return 0;
}
cs


저작자표시

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

[14649] 문홍안  (0) 2017.07.27
[10986] 나머지 합  (0) 2017.07.24
[5527] 전구 장식  (0) 2017.07.05
[14499] 주사위 굴리기  (0) 2017.04.16
[5624] 좋은 수  (0) 2017.04.06

+ Recent posts

티스토리툴바