'분류 전체보기' 카테고리의 글 목록 (10 Page)

분류 전체보기

백준 13414 수강신청

2018. 8. 2. 10:57

<링크>

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

<소스코드>

#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";
}

Colored by Color Scripter

<풀이>

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

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

맨뒤부터

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

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

순으로 들어왔으면

뒤부터 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

백준 13413 오셀로 재배치

2018. 8. 1. 01:40

<링크>

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);
    }
}
Colored by Color Scripter
cs

<풀이>

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

OXOX

XOXO

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

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

백준 2251 물통

2018. 8. 1. 01:16

<링크>

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

<소스코드>

#include<stdio.h>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
int isVisited[201][201][201];
vector<int> ans;
typedef struct status {
    int h[3];
} status;
queue<status> q;
void bfs();
int cap[3];
int main()
{
    for (int i = 0; i < 3; ++i)
        scanf("%d", &cap[i]);
    bfs();
    sort(ans.begin(), ans.end());
    for (int i = 0; i < ans.size(); ++i)
        printf("%d ", ans[i]);
}
void bfs()
{
    isVisited[0][0][cap[2]] = 1;
    q.push({ 0,0,cap[2] });
    while (!q.empty())
    {
        status cur = q.front();
        q.pop();
 
        if (cur.h[0] == 0)
            ans.push_back(cur.h[2]);
        for (int i = 0; i<3; ++i)
            for (int j = 0; j < 3; ++j)
            {
                if (cur.h[i] == 0)
                    continue;
                if (i != j)
                {
                    int tmp[3];
                    for (int k = 0; k < 3; ++k)
                        tmp[k] = cur.h[k];
                    if (cap[j] - tmp[j] <= tmp[i])
                    {
                        tmp[i]-=cap[j] - tmp[j];
                        tmp[j] = cap[j];
                    }
                    else
                    {
                        tmp[j] = tmp[j] + tmp[i];
                        tmp[i] = 0;
                    }
                    if (!isVisited[tmp[0]][tmp[1]][tmp[2]])
                    {
                        isVisited[tmp[0]][tmp[1]][tmp[2]] = 1;
                        q.push({ tmp[0],tmp[1],tmp[2] });
                    }
                }
                
            }
    }
}

Colored by Color Scripter

<풀이>

1. 물을 옮길때, 두 가지 특성을 고려한다.

A는 A통의 총량이고, a는 현재 A통에 있는 물의 양

B는 B통의 총량이고 ,b는 현재 B통에 있는 물의 양이라했을때

A->B로 물을 옮긴다고하면

B-b <= a 일때 : b=B, a= a-(B-b)

B-b > a 일때 : b=b+a, a=0

이렇게 된다.

●B통에 넣을수있는 물의 양이 a보다 같거나 작을때는, B에는 물이 꽉차게되고 a는 그만큼만 줄어든다.

A B
7  5 ...//총량
5  2 ...//현재량

A->B로 물을 부으면, 5-2=3보다 5가 크므로 b=5, a= 5-(5-2) = 2가 된다.

●B통에 넣을수있는 물의 양이 a보다 클 때에는, A의 물은 0이될때까지 붓게되고, b는 a만큼 늘어난다.

A B
7 8 ...//총량
3 2 ...//현재량

A->B로 물을 부으면, 8-2 =6이 3보다 크므로, a=0, b= 2+3 = 5가 된다.

2. A, B, C가 있으면 옮길수 있는 방향은 다음과 같이 6가지이다.

A->B

A->C

B->A

B->C

C->A

C->B

각각 물을 옮겨보고 이미 A,B,C에 남은양이 또 나오면 가지를 뻗어나가지 않는다.

8,0,2가 한번 나왔는데 또 8,0,2를 볼필요는 없기 때문이다.

3차원배열로 체크했다. 각 통의 물의 총량은 200이 최대이기 때문에

[200][200][200] 배열을 만들어도 메모리가 터지지 않는다.

8,0,2가 뜨면 [8][0][2]=1 이런식으로 체크했다.

3. 다른 BFS문제들과 다르게 최단횟수 등을 구하는게아니고

A가 0일 때, C의 가능한 양을 구하는 것이기 때문에

그냥 싹다 탐색한다.

아무리 심해도 200*200*200이 걸릴 것이다.

그럼 시간도 터지지 않는다.

저작자표시

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

백준 1525 퍼즐 (0)	2018.07.31
백준 9019 DSLR (0)	2018.07.31
백준 1963 소수 경로 (2)	2018.07.30
백준 1697 숨바꼭질 (1)	2018.07.29
KOITP 보물찾기 (0)	2018.07.23

백준 1525 퍼즐

2018. 7. 31. 11:13

<링크>

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

<소스코드>

#include<stdio.h>
#include<queue>
#include<set>
#include<string>
#include<iostream>
using namespace std;
queue<string> q;
set<int> isVisited;
int to[4] = { -1,1,-3,3 };
int bfs(string);
int main()
{
    string start;
    int n;
    for (int i = 0; i < 9; ++i) {
        scanf("%d", &n);
        start += n + '0';
    }
    printf("%d",bfs(start));
 
}
int bfs(string s)
{
    int depth = 0;
    q.push(s);
    isVisited.insert(stoi(s));
    while (!q.empty())
    {
        int size = q.size();
        for (int i = 0; i < size; ++i)
        {
            string cur = q.front();
            q.pop();
            if (cur.compare("123456780")==0)
                return depth;
 
            int zero;
            for (int j = 0; j < 9; ++j) //0의위치를 알아내고
                if (cur[j] == '0')
                {
                    zero = j; break;
                }
            for (int j = 0; j < 4; ++j)
            {
                if (j < 2)
                    if ((zero + to[j]) / 3 != zero / 3) continue;
                if (zero + to[j] >= 0 && zero + to[j] < 9)
                {                    
                    string toStr = string(cur);
                    swap(toStr[zero + to[j]], toStr[zero]);
                    int toNum = stoi(toStr);
                    if (isVisited.find(toNum) == isVisited.end())
                    {
                        isVisited.insert(toNum);
                        q.push(toStr);
                    }
                }
            }
        }
        ++depth;
    }
    return -1;
}

Colored by Color Scripter

<풀이>

1. 방문했는지 안했는지 여부를 set을 이용해 구현했다. 판때기에 있는 숫자들을 한줄로 쫙 깐다음에 하나의 정수로 표현한다.

1 2 3

4 5 6

7 8 0

: 123456780

0 1 3

2 4 6

5 8 7

: 13246587

2. 하나의 노드는 string으로 표현했다.

3. string상에서 '0'의 위치를 찾아내고 그 상하좌우에 있는 수와 자리를 바꾼뒤, bfs를 이어간다.

상,하는 -3, +3을 하면 된다.

좌,우는 -1, +1을 하되, 같은 라인에 있는지 확인해야한다.

index / 3이 같으면 같은 라인에 있는것이다.

string상에서의 인덱스 : 012345678 

판떼기 상에서의 인덱스 :
012 : /3 =0
345 : /3 =1
678 : /3 =2

4. java 라이브러리를 통해 구현한다면

HashSet의 contains메소드를 쓰면될것같다.

저작자표시

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

백준 2251 물통 (0)	2018.08.01
백준 9019 DSLR (0)	2018.07.31
백준 1963 소수 경로 (2)	2018.07.30
백준 1697 숨바꼭질 (1)	2018.07.29
KOITP 보물찾기 (0)	2018.07.23

백준 9019 DSLR

2018. 7. 31. 08:23

<링크>

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

<소스코드>

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<string>
#include<math.h>
#include<stack>
#include<string.h>
using namespace std;
void bfs(int, int);
void trace(pair<int,int>[], int);
int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        int A, B;
        scanf("%d%d", &A, &B);
        bfs(A, B);
        printf("\n");
    }
}
void bfs(int A, int B)
{
    int isVisited[10000] = { 0, };
    pair<int, int> before[10000];
    queue<int> q;
    isVisited[A] = 1;
    before[A] = { -1,-1 };
    q.push(A);
    while (!q.empty())
    {
        int n = q.front();
        q.pop();
        if (n == B) {
            trace(before, B); return;
        }
        int to[4];
        to[0] = n * 2 % 10000;
        to[1] = n == 0 ? 9999 : n - 1;
        to[2] = n % 1000 * 10 + n / 1000;
        to[3] = n % 10 * 1000 + n / 10;
        for (int i = 0; i < 4; ++i)
            if (!isVisited[to[i]])
            {
                isVisited[to[i]] = 1;
                before[to[i]] = { i,n };
                q.push(to[i]);
            }
    }
}
void trace(pair<int,int> before[],int n)
{
    stack<int> st;
    while (before[n].first!=-1)
    {
        st.push(before[n].first);
        n = before[n].second;
    }
    while (!st.empty())
    {
        switch (st.top())
        {
        case 0:printf("D"); break;
        case 1:printf("S"); break;
        case 2:printf("L"); break;
        case 3:printf("R"); break;
        }
        st.pop();
    }
}
 
Colored by Color Scripter
cs

<풀이>

1. 나올 수 있는 숫자는 0~9999이다.

2. bfs를 해서 A에서 B까지 몇 번만에 가냐가 중요한게 아니고 가는 경로를 기록해야한다.

처음엔 그냥 연산자만 기록하면서 가려했는데 'D' 연산 때문에 애매해질 것 같았다.

예를 들어

D연산을 통해 100이라는 숫자가 되었다면

이전 숫자는 50일 수도 있고 5050일 수도 있기 때문이다.

3. before[10000] 배열을 만들어서 내 이전의 숫자와 연산을 저장했다.

어차피 한 번 방문한 노드는 다시 보지않기 때문에 겹칠일도 없고

before에 기록된 모든 숫자들은 다 최단거리로 온거니깐 믿고 참조하면 된다.

1234 →L 2341 →L 3412

before[1234] = {-1,-1}
before[2341] = {1234 , L}
before[3412] = {2341 , L}

4. B부터 시작해서 before[ ]를 계속 참조하며 A가 나올때까지 stack에 넣는다.

5. 싹다 pop하면 정순서가 나온다.

저작자표시

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

백준 2251 물통 (0)	2018.08.01
백준 1525 퍼즐 (0)	2018.07.31
백준 1963 소수 경로 (2)	2018.07.30
백준 1697 숨바꼭질 (1)	2018.07.29
KOITP 보물찾기 (0)	2018.07.23

PREV 1 ···7 8 9 10 11 12 13 ···17 NEXT

들짐승 프로그래밍