<링크>

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


<소스코드>

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<stdio.h>
#include<vector>
using namespace std;
pair<int, int> node[26];
void pre_order(int);
void in_order(int);
void post_order(int);
int main()
{
    int N;
    scanf("%d", &N);
    getchar();
    for (int i = 0; i < N; ++i)
    {
        char buf[7];
        fgets(buf, sizeof(buf), stdin);
        int cur = buf[0] - 'A';
        int l = buf[2] - 'A';
        int r = buf[4] - 'A';
        node[cur].first = node[cur].second = -1;
        if (l != '.'-'A')
            node[cur].first = l;
        if (r != '.'-'A')
            node[cur].second = r;
    }
    pre_order(0);
    printf("\n");
    in_order(0);
    printf("\n");
    post_order(0);
}
void pre_order(int i)
{
    if (i == -1)
        return;
    printf("%c", i + 'A');
    pre_order(node[i].first);
    pre_order(node[i].second);
}
void in_order(int i)
{
    if (i == -1)
        return;
    in_order(node[i].first);
    printf("%c", i + 'A');
    in_order(node[i].second);
}
void post_order(int i)
{
    if (i == -1)
        return;
    post_order(node[i].first);
    post_order(node[i].second);
    printf("%c", i + 'A');
}
cs


<풀이>

pair 배열을 만들고 first는 left child, second는 right child를 나타냈다.


저작자표시

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

백준 8979 올림픽  (0) 2018.08.29
백준 2621 카드게임  (0) 2018.08.28
백준 13414 수강신청  (0) 2018.08.02
백준 13413 오셀로 재배치  (0) 2018.08.01
백준 10973 이전 순열  (0) 2018.07.24

<링크>

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


<소스코드>

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
#include<stdio.h>
int main()
{
    int t[1000000];
    int N, M;
    scanf("%d%d", &N, &M);
    for (int i = 0; i < N; ++i)
        scanf("%d", t + i);
    int l = 0, r = 1000000000;
    int ans = 0;
    while (l <= r)
    {
        int m = (l + r) / 2;
        long long s = 0;
        for (int i = 0; i < N; ++i)
            if (t[i] > m)
                s += t[i] - m;
        if (s >= M)
        {
            ans = m;
            l = m + 1;
        }
        else
            r = m - 1;
    }
    printf("%d", ans);
}
cs


<풀이>

이분탐색으로 찍어본 높이 하나당 모든 나무를 살펴봐야하기 때문에

시간복잡도는 

이 된다.

만약 벌어들인 나무가 M이상이면 높이를 더 높여봐야하고, 그럴때마다 답이 갱신된다.

M보다 못벌었으면 높이를 더 낮춰야한다.

저작자표시

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

백준 13423 Three Dots  (0) 2018.08.02
백준 1939 중량제한 :: 들짐승  (0) 2018.07.23
백준 3079 입국심사 :: 들짐승  (0) 2018.07.22

<링크>

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


<소스코드>

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
#include<stdio.h>
#include<stack>
#include<string.h>
using namespace std;
stack<int> st;
int main()
{
    char buf[100];
    int num;
    int N;
    scanf("%d", &N);
    while (N--)
    {
        scanf("%s", buf);
        if (strcmp(buf, "push") == 0)
        {
            scanf("%d", &num);
            st.push(num);
        }
        else if (strcmp(buf, "top") == 0)
        {
            if (st.size())
                printf("%d\n", st.top());
            else
                printf("-1\n");
        }
        else if (strcmp(buf, "size") == 0)
            printf("%d\n", st.size());
        else if (strcmp(buf, "empty") == 0)
        {
            if (st.size() == 0)
                printf("1\n");
            else
                printf("0\n");
        }
        else if (strcmp(buf, "pop") == 0)
        {
            if (st.size())
            {
                printf("%d\n", st.top());
                st.pop();
            }
            else
                printf("-1\n");
            
        }
    }
}
cs


<풀이>

시키는대로 하면 된다.


저작자표시

'알고리즘 풀이 > 스택,큐' 카테고리의 다른 글

백준 10845 큐  (0) 2018.08.29

<링크>

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


<소스코드>

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
#include<stdio.h>
#include<queue>
#include<string.h>
using namespace std;
int main()
{
    int N;
    scanf("%d", &N);
    char buf[100];
    deque<int> q;
    while (N--)
    {
        scanf("%s", buf);
        if (strcmp(buf, "push") == 0)
        {
            int n;
            scanf("%d", &n);
            q.push_back(n);
        }
        if (strcmp(buf, "pop") == 0)
        {
            if (q.size() == 0)
                printf("-1\n");
            else
            {
                printf("%d\n", q.front());
                q.pop_front();
            }
        }
        if (strcmp(buf, "front") == 0)
        {
            if (q.size() == 0)
                printf("-1\n");
            else
                printf("%d\n", q.front());
        }
        if (strcmp(buf, "back") == 0)
        {
            if (q.size() == 0)
                printf("-1\n");
            else
                printf("%d\n", q.back());
        }
        if (strcmp(buf, "size") == 0)
            printf("%d\n", q.size());
        if (strcmp(buf, "empty") == 0)
        {
            if (q.size() == 0)
                printf("1\n");
            else
                printf("0\n");
        }
 
    }
    
}
cs


<풀이>

좀더 편한 라이브러리인 deque를 이용했다.


저작자표시

'알고리즘 풀이 > 스택,큐' 카테고리의 다른 글

백준 10828 스택  (0) 2018.08.29

<링크>

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


<소스코드>

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<algorithm>
using namespace std;
typedef struct C {
    int n, g, s, b,r;
} C;
int compare(C c1, C c2)
{
    if (c1.g != c2.g)
        return c1.g > c2.g;
    if (c1.s != c2.s)
        return c1.s > c2.s;
    if (c1.b != c2.b)
        return c1.b > c2.b;
}
int main()
{
    C arr[1000];
    int N, K;
    scanf("%d%d", &N, &K);
    for (int i = 0; i < N; ++i)
    {
        int a, b, c, d;
        scanf("%d%d%d%d", &arr[i].n, &arr[i].g, &arr[i].s, &arr[i].b);
    }
    sort(arr, arr + N, compare);
    int i = 0;
    while (i < N)
    {
        int j = i;
        while (j < N && arr[j].g == arr[i].g && arr[j].s == arr[i].s && arr[j].b == arr[i].b)
        {
            arr[j].r = i;
            ++j;
        }
        i = j;
    }
    for(int i=0;i<N;++i)
    {
        if (arr[i].n == K)
            printf("%d", arr[i].r + 1);
    }
}
cs


<풀이>

처음엔 점수로 환산해서 풀어볼까 생각했지만 

금:10점 은:5점 동:2점 이런식으로하면

은메달이 3개면 금메달 1개딴 나라보다 등수가 높아지게 된다.

여기서 생각을 멈췄기 때문에 노가다로 풀었다.


하지만 아무리 은메달을 많이 따도 금메달 1개 점수보다 작게끔 만들면 얘기가 달라진다.


메달 총개수는 100만개이므로 적절한 선을 찾으면 된다.

금메달 1개, 은메달 99만9999개를 땄을때

금메달의 점수가 은메달의 점수보다 100만배이상 차이나면 가능하다.

은메달과 동메달도 마찬가지다


동메달 : 1점

은메달 : 10^6점

금메달 : 10^12점 이면 충분히 가를 수 있다.


그렇게 총점을 환산한 후 나보다 잘한 국가들이 몇개있는지만 찾아주면 된다.


<소스코드>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <stdio.h>
long long a[1001];
int main() {
    int N, K;
    scanf("%d%d", &N, &K);
    for (int i = 1; i<=N; ++i) {
        int n, g, s, b;
        scanf("%d%d%d%d", &n, &g, &s, &b);
        a[n] = g* 1e12 + s* 1e6 + b;
    }
    int ans = 1;
    for (int i = 1; i <=N; ++i) {
        if (a[i] > a[K]) ++ans;
    }
    printf("%d", ans);
    return 0;
}
cs


저작자표시

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

백준 1991 트리 순회  (0) 2018.08.31
백준 2621 카드게임  (0) 2018.08.28
백준 13414 수강신청  (0) 2018.08.02
백준 13413 오셀로 재배치  (0) 2018.08.01
백준 10973 이전 순열  (0) 2018.07.24

+ Recent posts

티스토리툴바