<링크>

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/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

<링크>

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


<소스코드>

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
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;
int main() {
    int ans = 0;
 
    vector<pair<int,char>> card;
    int cnt[10] = { 0, };
    string buf;
    int maxNum = 0;
    for (int i = 0; i < 5; ++i)
    {
        getline(cin, buf);
        char c = buf[0];
        int n = buf[2] - '0';
        card.push_back({ n,c}); //숫자, 색깔
        maxNum = max(maxNum,n);
        cnt[n]++;
    }
 
 
 
    int colorCheck = 1;
    int seqCheck = 1;
    sort(card.begin(), card.end());
    char c = card[0].second;
    for (int i = 1; i < 5; ++i)
    {
        if (c != card[i].second)
            colorCheck = 0;
        if (card[i].first != card[i - 1].first + 1)
            seqCheck = 0;
    }
    if (colorCheck)
        ans = max(ans, 600 + maxNum);
    if (seqCheck)
        ans = max(ans, 500 + maxNum);
    if (colorCheck && seqCheck)
        ans = max(ans, 900 + maxNum);
 
    vector<pair<int, int>> v;
    for (int i = 1; i <= 9; ++i)
        if (cnt[i])
            v.push_back({cnt[i],i });
    sort(v.begin(), v.end(),greater<pair<int,int>>());
    
    if (v[0].first >= 4)
        ans = max(ans,v[0].second + 800);
    else if (v[0].first == 3)
    {
        if (v[1].first == 2)
            ans = max(ans,v[0].second * 10 + v[1].second + 700);
        else
            ans = max(ans,v[0].second + 400);
    }
    else if (v[0].first == 2)
    {
        if (v[1].first == 2)
        {
            int m = max(v[0].second, v[1].second);
            int n = min(v[0].second, v[1].second);
            ans = max(ans,m * 10 + n + 300);
 
        }
        else
            ans = max(ans,v[0].second + 200);
    }
    else
        ans = max(ans,maxNum + 100);
    
    printf("%d", ans);
 
}
cs


<풀이>

걍 조건문 잘 만드는 문제인데 낚시가 있을것같았다. 

예를들어 R5, Y5, G7, B5, Y7 일때, 

같은숫자가 3개&2개인데 2개&2개도 적용이 된다. 

상식상 카드게임할때 3&2가 2&2보다 더 운좋은거니까 높은점수를 먹을것같았는데

2개&2개로 계산하는게 10을 곱하고 어쩌고가 있어서 더 클수도있을것같았다.

그래서 규칙들을 적용했을 때 나올수 있는 점수 범위를 보니까

<규칙 : 나올수있는점수>

●9번규칙 : 101~109점
●8번규칙(2) : 201~209점
●7번규칙(2&2) : 311~399점
●6번규칙(3) : 401~409점
●3번규칙(3&2) : 711~799점
●2번규칙(4) : 801~809점

하위규칙에서 아무리 잘나와봤자 상위규칙의 제일 못한놈을 이길수는 없다.

그래서 규칙적용 순서만 잘 적용시키면 최대점수를 알수있게 된다.


<카드 숫자 빈도 : 규칙>

●5 : 2번규칙
●4 1 : 2번규칙
●3 2 : 3번규칙
●3 1 1 : 6번규칙
●2 2 1 : 7번규칙
●2 1 1 1 : 8번규칙
●1 1 1 1 1 : (1 or 4 or 5 or 9번규칙)

저작자표시

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

백준 1991 트리 순회  (0) 2018.08.31
백준 8979 올림픽  (0) 2018.08.29
백준 13414 수강신청  (0) 2018.08.02
백준 13413 오셀로 재배치  (0) 2018.08.01
백준 10973 이전 순열  (0) 2018.07.24

<링크>

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


<소스코드>

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<set>
#include<iostream>
#include<string>
using namespace std;
set<string> s;
vector<string> seq;
vector<string> list;
int main()
{
    char buf[10];
    int K, L;
    scanf("%d%d", &K, &L);
    for (int l = 0; l < L; ++l)
    {
        string str;
        cin >> str;
        list.push_back(str);
    }
    for(int l=L-1;l>=0;--l)
    {
        string str = list[l];
        if (s.find(str) == s.end())
        {
            s.insert(str);
            seq.push_back(str);
        }
    }
 
    int size = seq.size();
    for (int i = size-1; i >=size-K && i>=0; --i)
        cout << seq[i]<<"\n";
}
cs


<풀이>

일단 들어온 학번들을 쫙 저장해놓고 맨 뒤부터 확인한다.

여러번 나온 같은 학번중, 앞에나온 학번은 의미가 없고 맨 마지막에나온 학번만 의미가 있기 때문이다.

맨뒤부터

set에 없으면 set에 넣어주고 리스트에도 넣어준다. 

set에 있으면 그냥 지나친다.

1
2
3
2
순으로 들어왔으면
뒤부터 2,3,1이 list에 들어가게 된다.

결국 리스트에는 꼴찌부터 1등까지의 목록이 남게된다.

그럼 다시 리스트의 끝에서부터 K개만 출력해야 1등부터 K등까지 출력된다.

이 때, K가 총 수강신청학생보다 클수있으므로 주의해야한다.

10명 제한인데 4명만 신청했으면 1,2,3,4등 다 수강신청하게 해줘야하기 때문이다.

저작자표시

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

백준 8979 올림픽  (0) 2018.08.29
백준 2621 카드게임  (0) 2018.08.28
백준 13413 오셀로 재배치  (0) 2018.08.01
백준 10973 이전 순열  (0) 2018.07.24
백준 10972 다음 순열  (1) 2018.07.24

<링크>

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


<소스코드>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<stdio.h>
int main()
{
    char c1[100001], c2[100001];
    int T;
    scanf("%d", &T);
    while (T--)
    {
        int N; scanf("%d", &N);
        scanf("%s", c1);
        scanf("%s", c2);
        int wbCnt=0, bwCnt = 0;
        for (int i = 0; i < N; ++i)
        {
            if (c1[i] == 'W' && c2[i] == 'B')
                ++wbCnt;
            else if (c1[i] == 'B' && c2[i] == 'W')
                ++bwCnt;
        }
        printf("%d\n", wbCnt < bwCnt ? bwCnt : wbCnt);
    }
}
cs


<풀이>

백말(W)은 O, 흑말(B)는 X로 표시하면

OXOX

XOXO

이런식으로 되어있을 때, 즉

O      X

X 와  O  가 엇갈려있을 때 바꿔주면 된다.


따라서 

O

X

랑


X

O

의 개수를 각각 세어서 1번연산을 이용해 한쌍으로 매칭시켜주면 된다.

그 후 다 매칭시키고 나서 더이상 짝지어줄 수 있는 애들이 없으면 그냥 2번 연산을 이용해 바꾼다.


ex)

OXOOXX

XOXOOO


굵은애들은 윗라인 애들을 1번연산으로 맞바꿔주면 된다.

빨간애는 남은 나가리인데 걔는 2번연산으로 바꿔주면된다.

저작자표시

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

백준 2621 카드게임  (0) 2018.08.28
백준 13414 수강신청  (0) 2018.08.02
백준 10973 이전 순열  (0) 2018.07.24
백준 10972 다음 순열  (1) 2018.07.24
백준 2725 보이는 점의 개수:: 들짐승  (0) 2018.07.22

+ Recent posts

티스토리툴바