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

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


흠흠...

사실 최단 거리라기 보다는.. 가장 비용을 적게 들여서(가장 벙커를 적게 방문하면서) 목적지로 도달하는 문제입니다.


처음에 접근은 이분탐색으로 했습니다.

벙커들을 sort하여 갈 수 있는 시간내로 이동할 수 있는 최대 거리로 이동을 하여서 목적지에 도달하게 했습니다.


이 문제에서 이분탐색을 쓰면 생기는 오류는 방향입니다.

x, y 좌표가 있기 때문에 방향이 있어서 최대한의 거리가 절대값이기 때문에 오류가 발생합니다.


그래서 dfs로 해결하려 했으나 dfs는 최적의 해를 보장해주지 않기 때문에 완전 탐색을 해야만합니다.

시간초과로 실패했습니다.


해결 방법은 bfs 혹은 다익스트라로 해결하시면 됩니다.

사실 해보니깐.. 다익스트라는 딱히 필요없는듯.. 어차피 bfs는 최적을 보장하기 때문에.......


풀 코드입니당.

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
#include <cstdio>
#include <queue>
 
using namespace std;
 
#define mp make_pair
#define ll long long
 
vector<pair<double, double> > b;
bool visit[1005];
int v, m;
double xs, ys;
double xt, yt;
 
double distance(pair<double, double> a, pair<double, double> b) {
    double x = a.first - b.first;
    double y = a.second - b.second;
    return x*x + y*y;
}
 
int main() {
    scanf("%d %d", &v, &m);
    scanf("%lf %lf", &xs, &ys);
    scanf("%lf %lf", &xt, &yt);
 
    double ttx, tty;
    while (~scanf("%lf%lf", &ttx, &tty)) {
        b.push_back(mp(ttx, tty));
    }
    b.push_back(mp(xt, yt)); //도착점 삽입
 
    queue<pair<int, pair<double, double> > > q;
    q.push(mp(0, mp(xs, ys)));
    
    ll md = v * m * 60; // 이동할 수 있는 최대거리
    md *= md; // 최대거리의 제곱
 
    while (!q.empty()) {
        int cnt = -q.front().first;
        double x = q.front().second.first;
        double y = q.front().second.second;
        q.pop();
 
        if (x == xt && y == yt) {
            printf("Yes, visiting %d other holes.\n", cnt - 1);
            return 0;
        }
 
        for (int i = 0; i < b.size(); i++) {
            if (visit[i] || distance(mp(x, y), b[i]) > md) continue;
            visit[i] = 1;
            q.push(mp(-(cnt + 1), b[i]));
        }
    }
 
    puts("No.");
 
    return 0;
}
cs


저작자표시

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

[14588] Line Friends(small)  (0) 2017.07.23
[1507] 궁금한 민호  (0) 2017.07.08

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


input이 50만이기 때문에 일반적인 방법으로 해결할 수는 없습니다.


해결 알고리즘은! 해쉬!


문제 해결 절차는

1. 인풋을 다받는다!


왜 다받고 시작하느냐!!!!!이게 더빠릅니다.. 인풋이 크면클수록 더 빠릅니다.

내부캐쉬?? 정확히는 잘모르는데 그렇대요...


2. 해쉬테이블에 인풋 데이터가 존재하는지 검사한다.

3. 2에서 존재한다면 해쉬테이블에 있는 인덱스를 갱신하고 갱신 전의 인덱스를 리턴한다.(해쉬테이블<pair<int, int> > = 학번(문자열로도 가능)과 인덱스)

4. 3에서 리턴 받은 인덱스의 데이터를 -1(문자열이라면 "")으로 만들어준다. 

5. 2에서 존재하지않으면 그냥 해쉬에 추가한다.

6. 1~5를 반복하고 끝나면 K만큼 출력한다.


cout.width(숫자) : 출력의 폭을 숫자로 하겠다.

cout.fill(문자 혹은 숫자) : 위에서 정한 폭이 안찼다면 문자 혹은 숫자로 가득 채우겠다.


아래는 코드입니다.

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 <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 10000
#define MAX_SIZE 10000
#define mp make_pair
#define pii pair<int, int>
 
using namespace std;
 
vector<pair<int, int> > myHash[MAX_SIZE];
int snum[500000];
 
int toNum(int a) {
    return a % MOD;
}
 
int f(int a, int idx) {
    int num = toNum(a);
 
    for (int i = 0; i < myHash[num].size(); i++) {
        if (myHash[num][i].first == a) {
            int tmp = myHash[num][i].second;
            myHash[num][i].second = idx;
            return tmp;
        }
    }
 
    myHash[num].push_back(mp(a, idx));
    return -1;
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int n, k;
    cin >> n >> k;
 
    for (int j = 0; j < k; j++) {
        cin >> snum[j];
    }
 
    for (int j = 0; j < k; j++) {
        int tmp = f(snum[j], j);
        if (tmp != -1) snum[tmp] = 0;
    }
 
 
    int cnt = 0;
    for (int j = 0; j < k; j++) {
        if (snum[j] != 0) {
            cout.width(8);
            cout.fill('0');   // 채움 문자는 '0'
            cout << snum[j] << '\n';
            cnt++;
            if (cnt == n) break;
        }
    }
 
    return 0;
}
 
 
cs


저작자표시

+ Recent posts

티스토리툴바