<링크>

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


<소스코드>

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
#include<stdio.h>
#include<vector>
#define MAX 201
using namespace std;
vector<int> want [MAX];
int visited[MAX];
int room[MAX];
int solve(int);
int main()
{
    int N, M;
    scanf("%d%d", &N, &M);
    for (int i = 1; i <= N; ++i)
    {
        int a, b;
        scanf("%d", &a);
        while (a--)
        {
            int b;
            scanf("%d", &b);
            want[i].push_back(b);
        }
    }
    int ans = 0;
    for (int i = 1; i <= N; ++i)
    {
        fill(visited,visited+N, 0);
        if (solve(i))
        {
            //for (int j = 1; j <= M; ++j)
            //    printf("%d ", room[j]);
            //printf("\n");
            ++ans;
        }
    }
    printf("%d", ans);
}
int solve(int c)
{
    if (visited[c])
        return 0;
    visited[c] = 1;
    for (int w : want[c]) //원하는방에 갈수있는지 체크
    {
        if (!room[w] || solve(room[w])) //방이 비어있거나, 원래있던놈을 밀어낼수있으면
        {
            room[w] = c;
            return 1;
        }
    }
    return 0;
}
cs


<풀이>

소를 1번소부터 순서대로 원하는 방에 들어갈 수 있는지 체크한다.

들어갈 수 있으면 총원을 늘려준다.

방이 비어있거나, 원래 방에 있던놈을 밀어낼 수 있으면 된다.

경우의 수를 다 셀 필요없이 들어갈수만 있으면 바로 재귀를 끝내버린다.


1번말이 원하는 방 : 2 5
2번말이 원하는 방 : 2 3 4
3번말이 원하는 방 : 1 5
4번말이 원하는 방 : 1 2 5
5번말이 원하는 방 : 2
<1번말이 들어갈때>
 방번호


1 


2


3


4


5




말번호


 


1


 


 


 




5번방에는 아직 안가봐도 된다. 걍 2번방이 비어있으니깐 ㅇㅋ여기다 이러고 다음말로 넘기면된다.
<2번말이 들어갈때>
 방번호
1 
2
3
4
5
말번호
 
2
 
 
 1
원래 2번방에있던 1번말을 5번방으로 밀어내고 자기가 들어간다.
<3번말이 들어갈때>
 방번호
1
2
3
4
5
말번호
3
2


 1
1번방이 비어있으니깐 ㅇㅋ개꿀 이러고 들어가면된다.
<4번말이 들어갈때>
원하는 1번방부터 보는데, 
1번방에 있던 3번말을 5번방으로 밀어내고
5번방에 있던 1번말을 2번방으로 밀어내고
2번방에 있던 2번말을 3번방으로 밀어낸다.

 방번호
1
2
3
4
5
말번호
4
1
2
 
3
<5번말이 들어갈때>
 방번호
1
2
3
4
5
말번호
4
1
2
 
3
밀고 밀어도 아무도 비켜줄수있는 말이 없으니깐 얘는 방을 차지할 수 없다.

visit로 체크하는 이유는

이미 밀린놈은 방에 없는걸로치는데 계속 밀어내면 무한루프에 빠지기 때문이다.

저작자표시

<링크>

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


<소스코드>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<stdio.h>
int coin[20];
int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        int N;
        scanf("%d", &N);
        for (int i = 0; i < N; ++i)
            scanf("%d", coin + i);
        int M;
        scanf("%d", &M);
        int dp[10001] = { 1, };
        for (int i = 0; i < N; ++i)
        {
            for (int j = coin[i]; j <= M; ++j)
                dp[j] += dp[j - coin[i]];
        }
        printf("%d\n", dp[M]);
    }
}
cs


<풀이>

가장 대표적인 다이나믹프로그래밍 유형 중의 하나이다. 

동전을 하나씩 집어서 1원~M원까지 만들수있는 경우의수를 만들어간다.

시간은 M*N이 된다.




 


저작자표시

'알고리즘 풀이 > DP' 카테고리의 다른 글

백준 1005 ACM Craft  (0) 2018.08.06
백준 9095 1,2,3 더하기  (0) 2018.07.26
백준 14501 퇴사 :: 들짐승  (1) 2018.07.22


 

 

<링크>

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

 

<풀이_1>

아무생각없이 하면 틀리는 이유는, 내가 완벽하지 못한데 다른 노드들을 갱신할 때 쓰이기 때문이다.

...-> A -> C ->...

...-> B -> C ->...

이렇게 둘이 있을 때 


아직 A가 완벽하게 갱신이 안돼서 최댓값을 못알아냈는데 C에게 정보를 제공해버렸다고 치자.

근데 나중에 A로 가는 다른 경로를 찾아서 A가 갱신이되면 C도 바꿔줘야되고 그 뒤로 연관된 모든놈들을 다 바꿔야된다.

그래서 나중에 피똥쌀 수가 있다. 그럼 A를 믿을수있게끔 만들어주는 방법은 A로 가는 모든경로들을 다 보면된다.

노드의 차수를 이용한다.

내 이전에 오는 노드들을 다 봤을때, 그 때 비로소 내가 다른 노드들을 갱신하는데 사용될 수 있게끔 했다.

 

<소스코드>

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
#include<stdio.h>
#include<vector>
#include<queue>
#include<algorithm>
#include<string.h>
using namespace std;
vector<int> adj[1001];
queue<int> q;
int time[1001];
int degree[1001];
int dp[1001];
int W;
void bfs();
int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        memset(dp, 0, sizeof(dp));
        memset(degree, 0, sizeof(degree));
        q = queue<int>();
        for (int i = 1; i <= 1000; ++i)
            adj[i] = vector<int>();
        int N, M;
        scanf("%d%d", &N, &M);
        for(int i=1;i<=N;++i)
            scanf("%d", time + i);
        while (M--)
        {
            int a, b;
            scanf("%d%d", &a, &b);
            adj[a].push_back(b);
            ++degree[b];
        }
        scanf("%d", &W);
 
        for (int i = 1; i <= N; ++i)
            if (degree[i] == 0)
            {
                q.push(i);
                dp[i] = time[i];
            }
        bfs();
        printf("%d\n", dp[W]);
    }
}
void bfs()
{
    while (degree[W] != 0)
    {
        int cur = q.front();
        q.pop();
        int s = adj[cur].size();
        for (int i = 0; i < s; ++i)
        {
            int to=adj[cur][i];
            dp[to] = max(dp[cur] + time[to], dp[to]);
            --degree[to];
            if (degree[to] == 0)
                q.push(to);
        }
    }
}
cs


<풀이_2>

목적지 W를 시작점으로 거꾸로 dfs하면 된다.

입력 받을때도 인접리스트를 싹다 거꾸로 받아주면 역방향 그래프가 완성된다.

연결리스트가 없는 끝노드까지 가면 걔는 시작건물이니깐 그냥 자기건물시간만 리턴해준다.

불필요한 재귀를 줄이기 위해 memozation을 사용했다.


<소스코드>

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<stdio.h>
#include<vector>
#include<algorithm>
#include<string.h>
using namespace std;
int dp[1001];
int t[1001];
vector<int> adj[1001];
int solve(int);
int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        memset(dp, -1, sizeof(dp));
        for (int i = 1; i <= 1000; ++i)
            adj[i].clear();
        int N, M;
        scanf("%d%d", &N, &M);
        for (int i = 1; i <= N; ++i)
            scanf("%d", t + i);
        while (M--)
        {
            int a, b;
            scanf("%d%d", &a, &b);
            adj[b].push_back(a);
        }
        int W;
        scanf("%d", &W);
        printf("%d\n",solve(W));
    }
}
int solve(int i)
{
    int &ret = dp[i];
    if (ret != -1)
        return ret;
    int m = 0;
    for (int to : adj[i])
        m = max(m, solve(to));
    return ret = m + t[i];
}
cs


저작자표시

'알고리즘 풀이 > DP' 카테고리의 다른 글

백준 9084 동전  (0) 2018.08.17
백준 9095 1,2,3 더하기  (0) 2018.07.26
백준 14501 퇴사 :: 들짐승  (1) 2018.07.22

<링크>

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


<소스코드>

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
#include<stdio.h>
#include<queue>
#include<vector>
#include<stack>
using namespace std;
priority_queue<pair<int,int>> pq; //pair<cost,node>
vector<pair<int, int>> adj[1001]; //pair<node,cost>
void dijkstra();
int N, M;
int dist[1001];
int before[1001];
int main()
{
    scanf("%d%d", &N, &M);
    while (M--)
    {
        int a, b,c;
        scanf("%d%d%d", &a, &b, &c);
        adj[a].push_back({ b,c });
    }
    dijkstra();
    printf("%d\n", dist[1]);
    stack<int> st;
    int i = before[1];
    while (i != 1)
    {
        st.push(i);
        i = before[i];
    }
    
    printf("1 ");
    while (!st.empty()) {
        printf("%d ", st.top());
        st.pop();
    }
    printf("1");
 
}
void dijkstra()
{
    int m = -999999;
    
    for (int i = 1; i <= N; ++i)
        dist[i] = m;
    dist[1] = 0;
    pq.push({ 0,1 });
    while (!pq.empty())
    {
        int cur=pq.top().second;
        int cost = pq.top().first;
        pq.pop();
 
        if (dist[cur] > cost)
            continue;
        
        int s = adj[cur].size();
        for (int i = 0; i < s; ++i)
        {
            int toNode = adj[cur][i].first;
            int toCost = adj[cur][i].second;
            if (dist[toNode] < cost + toCost)
            {
                dist[toNode] = cost + toCost;
                before[toNode] = cur;
                if(toNode!=1)
                pq.push({ dist[toNode],toNode });
            }
        }
    }
    return ;
}
cs


<풀이>

기존에 최단경로를 찾는 다익스트라 방식을 반대로 바꿔주면 된다.

그래서 priority_queue를 있는그대로 사용하면 된다.

최단경로때는 싸이클을 걱정 안해도 됐었지만 

이거는 마지막에 1번노드를 지나쳐서 더 이동하면 무한대로 점수가 늘어나기 때문에

1번노드로 갈때는 값 갱신만 하고 큐에 넣지 않았다.

DP로도 풀수있는 문제이다.


<소스코드>

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
#include<stdio.h>
#include<queue>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std;
void bfs();
vector<pair<int, int>> adj[1001]; //<node,cost>
queue<int> q;
int before[1001];
int dp[1001];
int degree[1001];
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 });
        ++degree[b];
    }
    bfs();
    printf("%d\n", dp[1]);
    stack<int> st;
    int i = before[1];
    while (i != 1)
    {
        st.push(i);
        i = before[i];
    }
 
    printf("1 ");
    while (!st.empty()) {
        printf("%d ", st.top());
        st.pop();
    }
    printf("1");
    
}
void bfs()
{
    q.push(1);
    while (degree[1])
    {
        int cur = q.front();
        q.pop();
        int s = adj[cur].size();
        for (int i = 0; i < s; ++i)
        {
            int toNode = adj[cur][i].first;
            int toCost = adj[cur][i].second;
            --degree[toNode];
            if (dp[toNode] < dp[cur] + toCost)
            {
                dp[toNode] = dp[cur] + toCost;
                before[toNode] = cur;
            }
            if (degree[toNode]==0)
                q.push(toNode);
        }
    }
}
cs

<풀이>

1번노드를 제외하고는 싸이클이 없으므로 이렇게 풀어도 될것같았다.

1. 차수를 미리 입력해놓는다.

2. 다음노드를 한번 확인할 때마다 다음노드의 차수를 하나 줄여준다.

3. 차수가 0이 되면 나한테 올 수 있는 노드들을 다 봤다는 뜻이다. 완벽하게 갱신됐다는 뜻이므로 다음 탐색을 위해 큐에 넣어준다.

저작자표시

<링크>

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


<소스코드>

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<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
int serch(int);
vector<int> v;
 
int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        v = vector<int>();
        int ans = 0;
        int N;
        scanf("%d", &N);
        for(int i=0;i<N;++i)
        {
            int tmp;
            scanf("%d", &tmp);
            v.push_back(tmp);
        }
        sort(v.begin(), v.end());
        for(int i=0;i<N-1;++i)
            for (int j = i + 1; j < N; ++j)
            {
                int d=v[j] - v[i];
                if (serch(v[j] + d))
                    ++ans;
            }
        printf("%d\n", ans);
    }
}
int serch(int target)
{
    int l = 0;
    int r = v.size() - 1;
    while (l <= r)
    {
        int m = (l + r) / 2;
        if (v[m] == target)
            return 1;
        
        if (v[m] > target)
            r = m - 1;
        else
            l = m + 1;
    }
    return 0;
}
cs


<풀이>

출제의도는 이분탐색인 것 같다. 두 점을 찍고, 나머지 한 점이 있는지 없는지 이분탐색으로 확인한다.

시간은 N^2*(logN)이 걸린다.

다른 풀이 방법도 있는데 


<소스코드>

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<stdio.h>
#include<algorithm>
using namespace std;
int dot[1000];
int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        int N;
        scanf("%d", &N);
        for (int i = 0; i < N; ++i)
            scanf("%d", dot + i);
        sort(dot, dot + N);
        int ans = 0;
        for (int i = 1; i < N - 1; ++i)
        {
            int l = 0;
            int r = N - 1;
            while (l < r)
            {
                int ldis = dot[i] - dot[l];
                int rdis = dot[r] - dot[i];
                if (ldis == rdis)
                {
                    ++ans;
                    ++l;
                }
                else if (ldis < rdis)
                    --r;
                else
                    ++l;
            }
        }
 
        printf("%d\n", ans);
    }
}
cs


<풀이>

s++ e--를 이용하는 방법이다. 가운데 점을 찍고, 좌측끝과 우측끝에서부터 간격을 비교하며

좌간이 넓으면 좌++ , 우간이 넓으면 우-- 한다.

이렇게 하면 중앙점한번 찍을때마다 모든 노드를 확인하기 때문에 N^2으로 끝낼 수 있다. 

저작자표시

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

백준 2805 나무 자르기  (0) 2018.08.30
백준 1939 중량제한 :: 들짐승  (0) 2018.07.23
백준 3079 입국심사 :: 들짐승  (0) 2018.07.22

+ Recent posts

티스토리툴바