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


저작자표시

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


으악..한 10번 틀렸네요...

문제를 잘읽읍시다..!



블록친 부분을 굉장히! 아주 잘 읽으셔야합니다.


저는 저 부분을 안읽고.. 내가 내려갈떄 내리막길이면 올라올떈 오르막길이니 어느방향에서 접근하냐에 따라 달라질 것이라고 생각했습니다.


삐삐!!!!!!!!

아니였습니다.


이 문제는 그냥 연결해라!!!!!!!!!!!!! 이 문제였습니다...

네!

MST.. 최소 스패닝 트리로 해결하는 문제입니다.


저는 크루스칼로 해결했습니다.


MST에는 크루스칼과 프림이 있는데 MST를 잘모르시는 분들은

공부를 하고 문제를 해결하시기 바랍니당!


간단하게 설명해드리자면! 싸이클이 생기지 않고 정점 n개를 간선 n - 1개로 연결하는 방법입니당!


크루스칼에서는 disjoint-set 알고리즘이 사용됩니당!

성능을 위해서는 우선순위-큐를 사용하시면 더 도움이 됩니다.!


이 문제는 input에서 오르막길이 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
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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#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 1001
#define mp make_pair
#define pii pair<int, int>
//ios::sync_with_stdio(false); cin.tie(0);
using namespace std;
 
int parent[MAX_SIZE];
int n, m;
vector<pair<pii, int> > edge;
 
int find(int x) {
    if (parent[x] == x) return x;
    else return parent[x] = find(parent[x]);
}
 
bool merge(int x, int y) {
    x = find(x);
    y = find(y);
    if (x != y) {
        parent[x] = y;
        return 1;
    }
 
    return 0;
}
 
int f(int mul) {
    priority_queue<pair<int, pii> > pq;
 
    for (int i = 0; i <= n; i++) parent[i] = i;
 
    for (int i = 0; i < edge.size(); i++) pq.push(mp(!edge[i].second * mul, mp(edge[i].first.first, edge[i].first.second)));
 
    int ret = 0;
    int cnt = 0;
 
    while (!pq.empty() && cnt <= n - 1) {
        int k = pq.top().first * mul;
        int from = pq.top().second.first;
        int to = pq.top().second.second;
        pq.pop();
 
        bool tmp = merge(from, to);
        if (tmp) {
            cnt++;
            ret += k;
        }
    }
 
    return ret;
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
 
    cin >> n >> m;
 
    for (int i = 0; i < m + 1; i++) {
        int a, b;
        bool c;
        cin >> a >> b >> c;
 
        edge.push_back(mp(mp(a, b), c));
    }
 
    int best = f(-1);
    int worst = f(1);
 
    cout << worst*worst - best*best;
 
    return 0;
}
 
cs


저작자표시

'알고리즘 > 최소 스패닝 트리(MST)' 카테고리의 다른 글

[1647] 도시 분할 계획  (0) 2017.08.30

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

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


처음엔 on과 off인 부분을 나눠서

그리디로 접근을 하려고 했었는데

1-2로 가는데 5, 2-3으로 가는데 20

1-4로 가는데 10, 4-5로 가는데 5이고, YNNNN, p = 3이라면

1-4-5 루트가 나와야하는데 1-2-3 루트가 나옵니다.


짱돌을 엄청나게 굴렸지만.... 생각이 잘안났습니다.

그래서 분류를 봤는데

dp와 비트마스크로 해결하는 문제였습니다.


저는 2차원 dp로 해결했습니다.

dp[on 발전소 갯수][발전소의 상태]라고 정의했습니다.

사실 발전소의 상태로 발전소의 개수를 알 수 있지만 편의를 위해 이렇게 해결했습니다.


문제에서 적어도 p개라고 했는데 p개 초과일 경우가 p개인 경우보다 코스트가 작아지는 경우는 없으므로

탈출조건은 발전소 갯수가 p이상일 때 탈출시켰습니다.


아래는 코드입니다.

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
#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 1000000
#define MAX_SIZE 16
#define mp make_pair
#define pii pair<int, int>
using namespace std;
 
int spend[MAX_SIZE][MAX_SIZE];
int dp[MAX_SIZE][1 << 16];
int n, p;
int on;
int onCnt;
 
int f(int cnt, int on) {
    if (cnt >= p) return 0;
 
    int &ret = dp[cnt][on];
    if (ret != -1) return ret;
    ret = INF;
 
    for (int i = 0; i < n; i++) {
        if(on & 1 << i){
            for (int j = 0; j < n; j++) {
                if (i == j || on & (1 << j)) continue;
                ret = min(ret, f(cnt + 1, on | 1 << j) + spend[i][j]);
            }
        }
    }
 
    return ret;
}
 
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 >> spend[i][j];
        }
    }
 
    for (int i = 0; i < n; i++) {
        char c;
        cin >> c;
        if (c == 'Y') on |= 1 << i, onCnt++;
    }
 
    cin >> p;
 
    memset(dp, -1, sizeof(dp));
 
    int ret = f(onCnt, on);
    cout << (ret == INF ? -1 : ret);
 
    return 0;
}
cs


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

[2225] 합 분해  (0) 2017.07.24
[2158] 동전 교환  (0) 2017.07.09
[2698] 인접한 비트의 개수  (0) 2017.07.04
[1029] 그림 교환  (0) 2017.06.27
[1915] 가장 큰 정사각형  (0) 2017.06.07

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



별 이상한 방법으로 엄청 시도했습니다..

dfs, bfs, 비트마스크 등등 ㅠㅠㅠㅠ....


해결 알고리즘은 플로이드-와샬을 이용하는 것입니다.


플로이드-와샬을 이용하면 모든 정점에 대한 최단거리를 테이블로 만들 수 있습니다.

잘모르시는 분들은 다른 블로그나 책을 통해서 공부하시고 참고해주시기 바랍니다.


input으로 들어오는 테이블이 현재 최단 거리 테이블이니

그 테이블을 기준으로 다시 한번 플로이드를 돌립니다.


이 때 중요한 것은

i - k - j(i에서 k를 거쳐 j로 가는 거리)가 i - j와 같다면

i - j간선, i - k간선, k-j간선 총 세개가 필요했던 것이

i - k, k - j 두 개의 간선으로 표현이 가능합니다.


플로이드를 통해서 이러한 간선을 전부 체크해준 후에

마지막에 체크되지 않은 간선 / 2 혹은 2차원 테이블에서 반만 더해준 후에 결과를 출력합니다.


-1이 출력되는 조건은 input으로 들어온 데이터가 최단거리가 아닐 때 입니다.


아래는 풀 코드입니다.


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 <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 1000000
#define MAX_SIZE 200
#define mp make_pair
#define pii pair<int, int>
using namespace std;
 
int spend[20][20];
int n;
 
int main() {
    cin >> n;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> spend[i][j];
        }
    }
 
    bool destroy[20][20] = { 0, };
    //플로이드
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j || i == k || k == j) continue;
                
                //삭제할 간선 찾기
                if (spend[i][j] == spend[i][k] + spend[k][j]) {
                    destroy[i][j] = 1;
                }
                //i, j가 최단거리가 아닐경우 -1 출력
                else if (spend[i][j] > spend[i][k] + spend[k][j]) {
                    puts("-1");
                    return 0;
                }
            }
        }
    }
 
    int ret = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            ret += !destroy[i][j] * spend[i][j];
        }
    }
 
    cout << ret;
 
    return 0;
}
cs


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

[14588] Line Friends(small)  (0) 2017.07.23
[1686] 복날  (0) 2017.07.12

+ Recent posts

티스토리툴바