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


저작자표시

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

+ Recent posts

티스토리툴바