<링크>

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


<소스코드>

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<cstdio>
#include<vector>
#include<math.h>
#include<algorithm>
using namespace std;
typedef pair<int, int> P;
vector<P> h,c,a; // 집, 치킨집, 남겨둘 치킨집
int N, M;
int ans = 1e9;
void check(vector<P> &a)
{
    if (a.size() == 0)
        return;
    int sum = 0;
    for (P i : h)
    {
        int m = 1e9;
        for (P j : a)
            m = min(m, abs(i.first - j.first) + abs(i.second - j.second));
        sum += m;
    }
    ans = min(ans, sum);
}
void recur(int i, int len)
{
    if (len <= M)
        check(a);
    if (i == c.size()||len>M)
        return;
    a.push_back(c[i]);
    recur(i + 1, len + 1);
    a.pop_back();
    recur(i + 1, len);
}
int main()
{
    scanf("%d%d", &N, &M);
    for(int i=0;i<N;++i)
        for (int j = 0; j < N; ++j)
        {
            int n;
            scanf("%d", &n);
            if (n == 1)
                h.push_back({ i,j });
            if (n == 2)
                c.push_back({ i,j });
        }
    recur(0,0);
    printf("%d", ans);
}
 
cs


<풀이>

1. 집 좌표 리스트, 치킨집 좌표 리스트를 미리 준비해둔다.

2. 재귀함수를 이용해서 치킨집 조합을 만든다.

i번째 치킨집을 포함하면 a벡터에넣고 재귀호출, 안하면 a.pop_back()으로 뺀 후 재귀호출하고

현재까지 찍은 치킨집 개수가 M개 이하이면 check()함수에 a벡터를 던져준다.

찍은 치킨집 개수가 M개를 넘어가거나 i가 총 치킨집 개수를 넘어가면 return한다.


3. chek()함수에는 내가 찍은 치킨집들의 좌표가 넘어오기 때문에 집 하나당, 찍힌 치킨집 전부를 보며 최솟값을 찾아 더해준다.

모든 집들에 대해 반복해서 더하면 찍은 치킨집들로 만든 도시의 치킨거리가 나온다.

이 값을 보고 답을 갱신한다.

저작자표시

'알고리즘 풀이 > 브루트 포스' 카테고리의 다른 글

백준 1107 리모컨  (2) 2018.07.26
KOITP 고장난시계  (0) 2018.07.23
백준 1421 나무꾼 이다솜 ::들짐승  (0) 2018.07.22
백준 14888 연산자 끼워넣기 :: 들짐승  (0) 2018.07.22

<링크>

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


<소스코드>

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
#include<stdio.h>
#include<queue>
#include<vector>
using namespace std;
int visit[1001];
vector<pair<int, int>> adj[1001];
priority_queue<pair<int, int>> q;//오는비용,노드
int main()
{
    int N, M;
    scanf("%d%d", &N, &M);
    while (M--)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        adj[a].push_back({ b,c });
        adj[b].push_back({ a,c });
    }
    q.push({ 0,1 });
    int ans = 0;
    while (!q.empty())
    {
        int cost = q.top().first;
        int node = q.top().second;
        q.pop();
        if (visit[node])
            continue;
        visit[node] = 1;
        ans += -cost;
    
        for (pair<int, int> p : adj[node])
        {
            int toCost = p.second;
            int toNode = p.first;
            q.push({ -toCost,toNode });
 
        }
    }
    printf("%d", ans);
}
cs


<풀이>

prim알고리즘을 적용했으며 priority_queue를 이용했다.

prim알고리즘은 greedy하게 현재 선택한 노드들에서 퍼져나갈 수 있는 간선들 중 가장 적은 비용의 간선을 택한다.

처음에 {0,1}을 넣어서 1번노드까지가는 비용 0을 넣어놓고

연결되어있으면 다 priority_queue에 넣어준다.

큐에 들어있는 쌍들은 {해당노드까지 가는 비용, 노드}인데 가장 작은값이 맨위에 올라와야하기 때문에 음수를 곱했다.

한번 방문한 노드는 또 볼필요없으므로 visit배열로 체크했다.

priority_queue의 맨위에는 현재 갈수있는 가장 가까운 정점이 떠올라와있기 때문에 선택하고, 해당 노드로 인해 추가되는 간선들을 다시 큐에 넣어주면 된다.


저작자표시

<링크>

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


<소스코드>

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
#include<stdio.h>
#include<vector>
#include<queue>
using namespace std;
vector<int> adj[32001];
queue<int> q;
int indegree[32001];
int main()
{
    int N, M;
    scanf("%d%d", &N, &M);
    while (M--)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        adj[a].push_back(b);
        ++indegree[b];
    }
    for (int i = 1; i <= N; ++i)
        if (indegree[i] == 0)
            q.push(i);
    while (!q.empty())
    {
        int c = q.front();
        printf("%d ", c);
        q.pop();
        for (int i : adj[c])
        {
            --indegree[i];
            if (indegree[i] == 0)
                q.push(i);
        }
    }
}
cs


<풀이>

차수를 기록하고 차수가 0인애들을 싹 큐에 집어넣는다.

큐에서 하나씩 빼면서 그 노드와 연결된 애들의 차수를 줄여주고, 차수가 0이되면 금마를 큐에 집어넣는다.


저작자표시

<링크>

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


<소스코드>

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
#include<stdio.h>
#include<string.h>
int parent[1000001];
int find(int i)
{
    if (parent[i] == i)
        return i;
    int j = find(parent[i]);
    parent[i] = j;
    return j;
}
void combine(int i, int j)
{
    parent[find(j)] = find(i);
}
int main()
{
    int N, M;
    scanf("%d%d", &N, &M);
 
    for (int i = 0; i <= N; ++i)
        parent[i] = i;
    while (M--)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        if (a == 0)
            combine(b, c);
        else
            if (find(b) == find(c))
                printf("YES\n");
            else
                printf("NO\n");
    }
}
 
cs


<풀이>

union find로 풀었다.

처음엔 시간초과가 났었다.


1
2
3
4
5
6
7
8
int find(int i)
{
    if (parent[i] == i)
        return i;
    int j = find(parent[i]);
    parent[i] = j;
    return j;
}
cs

find할때 부모를 다 갱신해서 부모자식간 depth가 1이 되게끔 갱신해야하는데 처음엔 그걸 빼먹었었다.
예를들어 
union(2,3)
unoin(3,4)
unoin(1,2) 순으로 쿼리가 들어오면
4의 부모는 3
3의 부모는 2
2의 부모는 1이 된다.
이때 4의 최종부모를 찾을때(find)는 1까지 거슬러올라가는데 3만큼 시간이 걸리고
3의 최종부모를 찾을때는 2만큼의 시간이 걸리게 되므로 극단적인 그래프가 그려지면 시간이 오래걸린다.
따라서 4의 부모를 find할때 1까지 거슬러올라갔으면 다시 리턴해 내려오면서 2의부모, 3의부모, 4의부모를 다 1로 바꿔줘야한다.



저작자표시

<링크>

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


<소스코드>

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
#include<stdio.h>
typedef long long ll;
ll tree[3000000];
ll num[1000001];
ll init(int, int, int);
void update(int, int, int, int, int);
ll sum(int, int, int, int, int);
int main()
{
    int N, M, K;
    scanf("%d%d%d", &N, &M, &K);
    for (int i = 1; i <= N; ++i)
        scanf("%lld", num + i);
    init(1, 1, N);
 
    for (int i = 0; i < M + K; ++i)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        if (a == 1)
        {
            int diff = c - num[b];
            num[b] = c;
            update(1, 1, N, b, diff);
        }
        else
            printf("%lld\n", sum(b, c, 1, 1, N));
    }
}
void update(int n, int s, int e, int t, int diff)
{
    if (s <= t && t <= e)
        tree[n] += diff;
    else
        return;
    if (s == e)
        return;
    int m = (s + e) / 2;
    update(n * 2, s, m, t, diff);
    update(n * 2 + 1, m + 1, e, t, diff);
}
ll sum(int l, int r, int n, int s, int e)
{
    if (l <= s && e <= r) //구하는구간이 노드의구간을 포함할때
        return tree[n];
    if (r < s || e < l) //아예 벗어나있을때
        return 0;
    //어중간하게 겹칠때
 
    int m = (s + e) / 2;
    return sum(l, r, n * 2, s, m) + sum(l, r, n * 2 + 1, m + 1, e);
}
ll init(int n, int s, int e)//n번노드는 s~e를 맡는다
{
    if (s == e)
        return tree[n] = num[s];
    int m = (s + e) / 2;
    tree[n] = init(n * 2, s, m) + init(n * 2 + 1, m + 1, e);
    return tree[n];
}
cs


<풀이>

세그먼트 트리 (Segment Tree)

https://www.acmicpc.net/blog/view/9


●init

n번노드는 s~e를 맡는다.

세그먼트트리를 만들때, 자식노드들은 n*2, n*2+1 로 퍼져나가고 각각이 맡는 범위는 s~절반, 절반+1~e까지이다.

노드 자체에 자신이 맡는 범위가 명시돼있지 않으므로 재귀 호출할 때 인자로 노드의 번호와 함께 맡는 범위를 같이 넘겨줘야한다. leaf노드까지 도달하면(s==e) 자기자신의 값을 저장하고 리턴한다.


●sum

합을 구할때는 해당노드가 맡는 범위(s~e)가 아예 구하고자하는 범위(l~r)에 속하지 않을때는 0을 리턴하고

완전 포함되어있을때는 그 노드의 값을 리턴한다.

위 둘중 하나가 아니라면

계속 반으로 쪼개서 재귀호출하여 리턴한다.


●update

해당노드가 포함되는 모든 노드들을 갱신시켜주면되는데 아예 포함되지 않을 경우는 그냥 리턴하고

leaf노드까지 도달하면(s==e) 리턴한다.

계속 반으로 쪼개서 재귀호출하고 수정한다.

여기서 깜빡하고 노드들의 합만 바꿔주고 배열 자체의 값은 바꾸지 않아서 많이 헤맸다.

저작자표시

+ Recent posts

티스토리툴바