시간 제한메모리 제한제출정답맞은 사람정답 비율
1 초128 MB127022916817.573%

문제

 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딫히면 게임이 끝난다.

게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다.

뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다.

  • 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.
  • 만약 이동한 칸에 사과가 있다면, 그대로 OK
  • 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다.(즉, 몸길이는 변하지 않는다.) 

사과의 위치와 뱀의 이동경로가 주어질 때 이 게임이 몇 초(seconds)후에 끝나는지 계산하라.

입력

첫째줄에 N이 주어진다. ( 2 ≤ N ≤ 100 )

다음줄에 사과의 개수 K가 주어진다.( 0 ≤ K ≤ 100 )

그리고 K개의 줄에는 사과의 위치가 주어지는데, 첫번째 숫자는 행(row), 두번째 숫자는 열(column) 위치를 의미한다. 맨위 맨좌측(1행 1열) 에는 사과가 없다.

그리고 뱀의 방향변환 개수 L 이 주어진다. ( 1 ≤ L ≤ 100 )

그리고 L개의 줄에는 뱀의 방향변환 정보가 주어지는데,  숫자 X와 문자 C로 이루어져 있다. X초 후에 왼쪽(C가 'L') 또는 오른쪽(C가 'D')로 방향을 변경 한다는 뜻이다. X는 10,000이하의 양의 정수이다.

출력

문제의 정답,  즉 초(seconds) 를 첫째줄에 출력하라.

예제 입력 

6
3
3 4
2 5
5 3
3
3 D
15 L
17 D

예제 출력 

9

힌트















맵을 배열로 선언할 수 있다는게 난이도가 높진 않았습니다.

알고리즘 분류는 구현보다는 시물레이션에 가까운 것 같네요..


사과의 위치는 맵에 2로 표현했고, 턴하는 위치는 v벡터에 sec와 꺽는 방향을 페어로 넣었습니다.


이 문제의 핵심은 뱀의 흔적을 저장하는 것입니다.


저는 간단하게 벡터에 저장했고, 맵이 0이라면

snake벡터의 맨 앞의 좌표에 해당하는 곳을 0으로 바꿔주고 맨 앞 벡터를 삭제했습니다.


아래의 코드입니다.


1
2
3
4
5
6
7
8
9
        if(nx < 0 || ny < 0 || nx >= N || ny >= N) break// 맵 벗어나는지 검사
 
        //맵검사
        if(map[nx][ny] == 1break;
        else if(map[nx][ny] == 0)
        {
            map[snake[0].first][snake[0].second] = 0;
            snake.erase(snake.begin());
        }
cs


그리고 2를 만나던 0을 만나던 머리 부분은 1로 갱신하고 백터의 맨뒤에 뱀의 머리 좌표를 삽입합니다.


1
2
3
4
5
//스네이크 머리 갱신 및 맵 갱신
        x = nx;
        y = ny;
        map[x][y] = 1;
        snake.push_back(mp(x, y));
cs




아래는 문제의 풀 코드입니다.


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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <cstdio>
#include <stack>
#define MAX_SIZE 100
#define MOD 1000000009
#define ull unsigned long long
#define ll long long
#define mp make_pair
 
using namespace std;
 
typedef pair<intint> p;
 
int N, K, L;
int map[MAX_SIZE][MAX_SIZE]; // 사과는 2, 뱀은 1, 맵은 0
vector<p> v; //sec, turn
 
int dx[4= {-1100};
int dy[4= {00-11};
 
//오른쪽 : 위 -> 오, 아래 -> 왼, 오 -> 아, 왼 -> 위
//왼쪽 : 위 -> 왼, 아래 -> 오른, 오 -> 위, 왼 -> 아
 
//r : 0 -> 3, 1 -> 2, 3 -> 1, 2 -> 0
//l : 0 -> 2, 1 -> 3, 3 -> 0, 2 -> 1
 
int turn(int now, int next)
{
    if(next == 0// 왼쪽
    {
        if(now == 0 || now == 1return (now + 2) % 4;
        else return 3 - now;
    }
    else // 오른쪽
    {
        if(now == 0 || now == 1return 3 - now;
        else return (now + 2) % 4;
    }
}
 
 
void input()
{
    scanf("%d %d"&N, &K);
 
    for(int i = 0; i < K; i++)
    {
        int x, y;
        scanf("%d %d"&x, &y);
        map[x - 1][y - 1= 2;
    }
 
    scanf("%d"&L);
 
    for(int i = 0; i < L; i++)
    {
        int s;
        char c;
 
        scanf("%d %c"&s, &c);
 
        int d;
        if(c == 'L') d = 0//왼
        else d = 1//오른쪽
 
        v.push_back(mp(s, d));
    }
}
 
void process()
{
    vector<p> snake;
 
    int x = 0, y = 0// 머리 위치
 
    int d = 3;
    int sec = 0;
 
    int vi = 0;//시간 벡터 인덱스
    bool v_flag = 0;//벡터가 끝나면 1이됨
 
    map[x][y] = 1;
    snake.push_back(mp(x, y));
 
    while(1)
    {
        if(!v_flag && sec == v[vi].first)
        {
            d = turn(d, v[vi++].second);
            if(vi == v.size()) v_flag = 1;
        }
 
        //다음 좌표
        int nx = x + dx[d];
        int ny = y + dy[d];
 
        if(nx < 0 || ny < 0 || nx >= N || ny >= N) break// 맵 벗어나는지 검사
 
        //맵검사
        if(map[nx][ny] == 1break;
        else if(map[nx][ny] == 0)
        {
            map[snake[0].first][snake[0].second] = 0;
            snake.erase(snake.begin());
        }
 
        //스네이크 머리 갱신 및 맵 갱신
        x = nx;
        y = ny;
        map[x][y] = 1;
        snake.push_back(mp(x, y));
 
        sec++;
    }
 
    printf("%d\n", sec + 1);
}
 
 
int main()
{
    input();
    process();
 
    return 0;
}
cs


'알고리즘 > 구현' 카테고리의 다른 글

[14499] 주사위 굴리기  (0) 2017.04.16
[5624] 좋은 수  (0) 2017.04.06
[1952] 달팽이2  (0) 2017.04.04
[2745] 진법 변환  (0) 2017.04.02
[3460] 이진수  (0) 2017.04.02

시간 제한메모리 제한제출정답맞은 사람정답 비율
2 초128 MB47826021656.397%

문제

M줄 N칸으로 되어 있는 표 위에, 달팽이 모양으로 선을 그리려고 한다.

  
   
   
   
   

위의 그림은 M=5, N=3의 예이다. 이제 표의 왼쪽 위 칸(ㅇ)에서 시작하여, 오른쪽으로 선을 그려 나간다. 표의 바깥 또는 이미 그려진 칸에 닿아서 더 이상 이동할 수 없게 되면, 시계방향으로 선을 꺾어서 그려나간다.

위의 표는 선을 그려 나간 모양을 나타낸 것이다. (선이 꺾어진 부분은 대각선으로 나타내었다. 표의 모든 칸이 채워질 때까지, 선을 몇 번 꺾게 될까?

입력

첫째 줄에 M과 N이 빈 칸을 사이에 두고 주어진다. (2≤M, N≤100)

출력

첫째 줄에 표의 모든 칸이 채워질 때까지 선이 꺾어지는 횟수를 출력한다.

예제 입력 

5 3

예제 출력 

5

힌트













예전에는 굉장히 어렵게 생각해서 실패했던 문제인데...

지금 푸니까 왜 이렇게 쉬울까요..


방향이 꺾이는 경우는 딱 두가지입니다.

1. 맵 밖으로 나간다.

2. 방문했던 곳이다.


예전엔 2번이 어려웠는데... 그냥 맵을 만들어서 방문표시하면 끝인데.. 왜어렵게 생각했을까요...

와일문 탈출조건은 

만약 방향을 꺾어서 이동했음에도 불구하고 방문한 곳이라면 모든 맵을 다 방문한 것입니다!!

그러므로 탈출하고 마지막에 꺾인 부분은 제외해야하므로 1을 뺴준것이 정답입니다.!


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
#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <cstdio>
#include <stack>
#define MAX_SIZE 100
#define MOD 1000000009
#define ull unsigned long long
#define ll long long
 
using namespace std;
 
 
bool visit[MAX_SIZE][MAX_SIZE];
int m, n;
int dx[4= {-1100};
int dy[4= {00-11};
//3 -> 1, 1 -> 2, 2 -> 0, 0 -> 3
//오 -> 아, 아 -> 왼, 왼 -> 위 , 위 -> 오
 
int set_direct(int d)
{
    if(d == 3 || d == 2return (d + 2) % 4;
    else return 3 - d;
}
 
 
int main()
{
 
    scanf("%d %d"&m, &n);
 
    int x=0, y=0;
    int d = 3;
    int ret = 0;
 
    while(1)
    {
        if(visit[x][y] == 1break;
 
        visit[x][y] = 1;
 
        int nx = x + dx[d];
        int ny = y + dy[d];
 
 
        if(visit[nx][ny] == 1 || nx < 0 || ny < 0 || nx >= m || ny >= n)
        {
            d = set_direct(d);
            nx = x + dx[d];
            ny = y + dy[d];
            ret++;
        }
 
        x = nx;
        y = ny;
    }
 
    printf("%d\n", ret - 1);
 
    return 0;
}
cs


'알고리즘 > 구현' 카테고리의 다른 글

[5624] 좋은 수  (0) 2017.04.06
[3190] 뱀  (0) 2017.04.05
[2745] 진법 변환  (0) 2017.04.02
[3460] 이진수  (0) 2017.04.02
[2399] 거리의 차이  (2) 2017.04.02

시간 제한메모리 제한제출정답맞은 사람정답 비율
1 초128 MB95221115624.111%

문제

아주 먼 미래에 사람들이 가장 많이 사용하는 대중교통은 하이퍼튜브이다. 하이퍼튜브 하나는 역 K개를 서로 연결한다. 1번역에서 N번역으로 가는데 방문하는 최소 역의 수는 몇 개일까?

입력

첫째 줄에 역의 수 N과 한 하이퍼튜브가 서로 연결하는 역의 개수 K, 하이퍼튜브의 개수 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ K, M ≤ 1000)

다음 M개 줄에는 하이퍼튜브의 정보가 한 줄에 하나씩 주어진다. 총 K개 숫자가 주어지며, 이 숫자는 그 하이퍼튜브가 서로 연결하는 역의 번호이다. 

출력

첫째 줄에 1번역에서 N번역으로 가는데 방문하는 역의 개수의 최소값을 출력한다. 만약, 갈 수 없다면 -1을 출력한다.

예제 입력 

9 3 5
1 2 3
1 4 5
3 6 7
5 6 7
6 8 9

예제 출력 

4

힌트















N을 입력받았다면 하이퍼튜브의 좌표를 N + 1부터 N + M + 1까지라고 생각했습니다.

하이퍼튜브와 일반 정점의 차이는 cost입니다.

하이퍼튜브로 가는 비용은 0이고 다른 정점으로 가는 비용은 1입니다.


그리고 다익스트라를 이용해서 N까지의 최소비용을 구하면 간단하게 해결할 수 있습니다.



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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <iostream>
#include <cstdio>
 
#include <algorithm>
#include <string.h>
 
#include <stack>
#include <vector>
#include <queue>
 
#define MAX_SIZE 102000
#define MOD 1000000009
#define ull unsigned long long
#define ll long long
#define mp make_pair
#define INF 0x7fffffff
 
using namespace std;
typedef pair<intint> p;
 
vector<int> v[MAX_SIZE];
 
int n, k, m;
int dist[MAX_SIZE];
bool visit[MAX_SIZE];
int pos;
 
 
 
void dijkstra()
{
    for(int i = 2; i < pos; i++) dist[i] = INF;
 
    priority_queue<p> pq; // - 로 값을 넣자
    pq.push(mp(-11));
 
    while(!pq.empty())
    {
        p pop_data = pq.top();
        pq.pop();
 
        int from = pop_data.second;
        int cnt = -pop_data.first;
 
        if(visit[from]) continue;
        visit[from] = 1;
 
        for(int i = 0; i < v[from].size(); i++)
        {
            int to = v[from][i];
            int add = 1;
 
            if(to > n) add--// 하이퍼 튜브면 -를 해서 cost를 0로 만든다.
 
            if(dist[to] > cnt + add)
            {
                dist[to] = cnt + add;
                pq.push(mp(-dist[to], to));
            }
        }
    }
}
 
 
int main()
{
    scanf("%d %d %d"&n, &k, &m);
 
 
    pos = n + 1// 하이퍼튜브 좌표
 
    for(int i = 0; i < m; i++)
    {
        for(int j = 0; j < k; j++)
        {
            int to;
            scanf("%d"&to);
            v[pos].push_back(to);
            v[to].push_back(pos);
        }
 
        pos++;
    }
 
    dijkstra();
    printf("%d\n", dist[n] == INF ? -1 : dist[n]);
    return 0;
}
 
cs


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

[5427] 불  (0) 2017.04.16
[13460] 째로탈출2  (2) 2017.04.16
[12100] 2048 easy  (0) 2017.04.16
[9009] 피보나치  (0) 2017.04.04
[9328] 열쇠  (0) 2017.04.02

시간 제한메모리 제한제출정답맞은 사람정답 비율
1 초128 MB111060348452.666%

문제

피보나치 수 ƒK는 ƒK = ƒK-1 + ƒK-2로 정의되며 초기값은 ƒ0 = 0과 ƒ1 = 1 이다. 양의 정수는 하나 혹은 그 이상의 서로 다른 피보나치 수들의 합으로 나타낼 수 있다는 사실은 잘 알려져 있다. 

하나의 양의 정수에 대한 피보나치 수들의 합은 여러 가지 형태가 있다. 예를 들어 정수 100은 ƒ4 + ƒ6 + ƒ11 = 3 + 8 + 89 또는 ƒ1 + ƒ3 + ƒ6 + ƒ11 = 1 + 2 + 8 + 89, 또는 ƒ4 + ƒ6 + ƒ9 + ƒ10 = 3 + 8 + 34 + 55 등으로 나타낼 수 있다. 이 문제는 하나의 양의 정수를 최소 개수의 서로 다른 피보나치 수들의 합으로 나타내는 것이다. 

하나의 양의 정수가 주어질 때, 피보나치 수들의 합이 주어진 정수와 같게 되는 최소 개수의 서로 다른 피보나치 수들을 구하라. 

입력

입력 데이터는 표준입력을 사용한다. 입력은 T 개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 테스트 데이터의 수를 나타내는 정수 T 가 주어진다. 각 테스트 데이터에는 하나의 정수 n이 주어진다. 단, 1 ≤ n ≤ 1,000,000,000. 

출력

출력은 표준출력을 사용한다. 하나의 테스트 데이터에 대한 해를 하나의 줄에 출력한다. 각 테스트 데이터에 대해, 피보나치 수들의 합이 주어진 정수에 대해 같게 되는 최소수의 피보나치 수들을 증가하는 순서로 출력한다. 

예제 입력 

4
100
200
12345
1003

예제 출력 

3 8 89
1 55 144
1 34 377 987 10946
3 13 987

힌트













N의 크기가 최대 1,000,000,000이기 때문에 피보나치 값이 저 수를 넘기위해서는 대략 40 몇이라는 것을 알 수 있었습니다.

완전탐색으로 한다면 40^2의 시간이 걸리기 때문에 제한 시간 1초에는 충분했습니다.


입력받은 N과 가장 근접한 작은 수를 찾아서 거기서 부터 값을 더해나갑니다.

만약 더할 때 N보다 커진다면 그 수를 빼고 그 다음으로 넘어갑니다.

그리고 더한 수를 순서대로 출력해야 하고 큰 수 부터 더했으므로 스택에 저장했습니다.


0까지 갔는데도 n을 못만들었다면 근접한 작은 수에서 1을 빼고 다시 탐색합니다.!


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
76
77
78
79
80
81
82
83
84
#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <cstdio>
#include <stack>
#define MAX_SIZE 100
#define MOD 1000000009
#define ull unsigned long long
#define ll long long
 
using namespace std;
ll fi[MAX_SIZE];
 
int main()
{
    //피보나치 값 미리 구하기
    fi[0= 1;
    fi[1= 1;
    for(int i = 2;; i++)
    {
        fi[i] = fi[i - 1+ fi[i - 2];
        if(fi[i] >= 1000000000break;
    }
 
    int n, t;
    scanf("%d"&t);
 
    while(t--)
    {
        scanf("%d"&n);
 
        int start;
        stack<ll> s; // 출력할 때 쓸 스택
 
        for(start = 0; fi[start] <= n; start++); // n과 가장 근접한 수 찾기
        start--//fi[start]값이 n을 넘었다면 그 전 값이 가장 근접한 작은 수이기 때문에 1 빼기.
 
        ll sum = 0;
        bool flag = 0;
 
        //탐색하기
        for(int i = start; i >= 0; i--)
        {
            for(int j = i; j >= 0; j--)
            {
 
                sum += fi[j];
                s.push(fi[j]);
 
                if(sum == n)
                {
                    flag = 1;
                    break;
                }
                else if(sum > n)
                {
                    sum -= fi[j];
                    s.pop();
                }
 
            }
 
            if(flag) break;
            else
            {
                sum = 0;
                while(!s.empty()) s.pop();
            }
        }
 
        while(!s.empty())
        {
            printf("%lld ", s.top());
            s.pop();
        }
        puts("");
 
    }
 
    return 0;
 
}
 
cs

나중에 읽었더니.. 제가 한 풀이는 완전 탐색이 아니고 그리디를 이용한 방법이네요...
그래서 완전 탐색으로 다시 한번 풀었습니다.
아래의 코드입니다.
dfs를 이용해서 완전탐색을 해보았습니다.


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
76
77
78
#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <cstdio>
#include <stack>
#define MAX_SIZE 100
#define MOD 1000000009
#define ull unsigned long long
#define ll long long
 
using namespace std;
int fi[MAX_SIZE];
int n, t;
stack<int> s;
bool flag;
 
void dfs(int idx, int sum)
{
    if(sum > n) return;
    else if(sum == n)
    {
        s.push(fi[idx]);
        while(!s.empty())
        {
            printf("%d ", s.top());
            s.pop();
        }
        puts("");
        flag = 1;
        return;
    }
 
    s.push(fi[idx]);
 
    for(int i = idx - 1; i >= 0; i--)
    {
        dfs(i, sum + fi[i]);
        if(flag) return;
    }
}
 
 
int main()
{
    fi[0= 1;
    fi[1= 1;
    for(int i = 2;; i++)
    {
        fi[i] = fi[i - 1+ fi[i - 2];
        if(fi[i] >= 1000000000break;
    }
 
 
    scanf("%d"&t);
 
    while(t--)
    {
        flag = 0;
        scanf("%d"&n);
 
        int start;
 
        for(start = 0; fi[start] <= n; start++);
        start--;
 
        for(int i = start; i >= 0; i--)
        {
            dfs(i, fi[i]);
            while(!s.empty()) s.pop();
            if(flag) break;
        }
 
    }
 
    return 0;
}
 
cs




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

[5427] 불  (0) 2017.04.16
[13460] 째로탈출2  (2) 2017.04.16
[12100] 2048 easy  (0) 2017.04.16
[5214] 환승  (0) 2017.04.04
[9328] 열쇠  (0) 2017.04.02

문제를 풀다보면 무언가에 반사되거나 부딪혀서 방향이 꺾이는 문제를 볼 수 있습니다.

아래의 그림이 예시입니다.



행을 x로, 열을 y로 쳤을 때


1
2
3
int dx[4= {-1100};
int dy[4= {00-11};
cs


dx[0], dy[0] 은 위, dx[1], dy[1]은 아래

dx[2], dy[2] 은 왼쪽, dx[3], dy[3]은 오른쪽

입니다.


처음에 문제를 이렇게 해결했었습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int move(int direct, int mirror)
{
    if(mirror == 0return direct;
    switch(direct)
    {
    case 0:
        if(mirror == 1return 3;
        else return 2;
        break;
    case 1:
        if(mirror == 1return 2;
        else return 3;
        break;
    case 2:
        if(mirror == 1return 1;
        else return 0;
        break;
    case 3:
        if(mirror == 1return 0;
        else return 1;
        break;
    }
}
cs


그림을 그려보고 방향과 반사되는 면에 일일이 경우를 나눴습니다.

그리고.. 다른 사람의 코드를 분석하던 중에.....


1
2
3
4
5
6
int move(int direct, int mirror)
{
    if(mirror == 0return direct;
    else if(mirror == 1return 3 - direct;
    else return (direct + 2) % 4;
}
cs


이렇게 간단한 소스를 찾을 수 있었습니다.

원리는 잘 모르겠으나... 하나씩 대입해보니 일치했습니다.

방향 변환하는 것이 자주 나오니깐... 이렇게 시간을 단축할 수 있겠습니다.!

'알고리즘 > 문제풀이 팁' 카테고리의 다른 글

scanf로 EOF까지 입력 받기 팁  (0) 2017.07.06

문제

시간 제한메모리 제한제출정답맞은 사람정답 비율
1 초128 MB233744526717.440%

상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 필요하다. 상근이는 일부 열쇠를 이미 가지고 있고, 일부 열쇠는 빌딩의 바닥에 놓여져 있다.

상근이가 훔칠 수 있는 문서의 최대 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 수는 100개를 넘지 않는다.

각 테스트 케이스의 첫째 줄에는 지도의 높이와 너비 h와 w (2 ≤ h, w ≤ 100)가 주어진다. 다음 h개 줄에는 빌딩을 나타내는 w개의 문자가 주어지며, 각 문자는 다음 중 하나이다.

  • '.'는 빈 공간을 나타낸다.
  • '*'는 벽을 나타내며, 상근이는 벽을 통과할 수 없다.
  • '$'는 상근이가 훔쳐야하는 문서이다.
  • 알파벳 대문자는 문을 나타낸다.
  • 알파벳 소문자는 열쇠를 나타내며, 그 문자의 대문자인 모든 문을 열 수 있다.

마지막 줄에는 상근이가 이미 가지고 있는 열쇠가 공백없이 주어진다. 만약, 열쇠를 하나도 가지고 있지 않는 경우에는 "0"이 주어진다.

상근이는 빌딩 밖으로 나갈 수 있다. 각각의 문에 대해서, 그 문을 열 수 잇는 열쇠의 개수는 0개, 1개, 또는 그 이상이고, 각각의 열쇠에 대해서, 그 열쇠로 열 수 있는 문의 개수도 0개, 1개, 또는 그 이상이다. 열쇠는 여러 번 사용할 수 있다.

출력

각 테스트 케이스 마다, 상근이가 훔칠 수 있는 문서의 최대 개수를 출력한다.

예제 입력 

3
5 17
*****************
.............**$*
*B*A*P*C**X*Y*.X.
*y*x*a*p**$*$**$*
*****************
cz
5 11
*.*********
*...*...*x*
*X*.*.*.*.*
*$*...*...*
***********
0
7 7
*ABCDE*
X.....F
W.$$$.G
V.$$$.H
U.$$$.J
T.....K
*SQPML*
irony

예제 출력 

3
1
0

힌트






































































문제를 읽었을 때, 굉장히 쉬운 문제라고 생각해서 낮은 정답률에 의아했습니다.

하지만 풀다보니까 열쇠가 없어서 방문하지 못한 곳의 열쇠를 나중에 얻었을 경우를

처리해주는 부분이 까다로웠습니다.


dfs를 써서 탐색을 한다면 동서남북 방향으로 이동할 때 키가 있으면 방문하면 되는 것이고,

없을 경우에는 벡터에 문의 좌표를 넣었습니다.

그리고 dfs탐색이 끝나면

벡터에 들어있는 문을 탐색하여 키를 얻는다면 한번 더 벡터의 처음부터 탐색을 하고,

만약 키를 얻을 수 없다면 while문을 종료하고 얻은 서류 값을 출력하면 됩니다.


추가로!!! 시작점이 없기 때문에 굉장히 고민했는데 방법은 간단합니다.


(0, 0)

 

 

 

 

 

 

(1, 1)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

(4, 4)

 

 

 

 

 

 

(5, 5)


h = 4, w = 4일 경우에 우리가 입력 받는 부분은 빨간색입니다.

(0, 0)부터 dfs로 탐색을 한다면 빨간색의 테두리에 문이라면 키가 있을 때 들어갈 수 있고,

없다면 벡터에 넣습니다.

'.'이라면 맵안으로 들어갈 것입니다.



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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include <cstdio>
#include <iostream>
#include <vector>
#include <string.h>
 
#define ll long long
#define MAX_SIZE 110
#define ALPHA_SIZE 26
using namespace std;
 
vector<pair<intint> > v;
 
int h, w;
char map[MAX_SIZE][MAX_SIZE];
bool visit[MAX_SIZE][MAX_SIZE];
bool key[ALPHA_SIZE];
int dx[4= {001-1};
int dy[4= {1-10,0};
bool flag;
 
void input()
{
    scanf("%d %d"&h, &w);
    getchar();
 
    for(int i = 1; i <= h; i++)
    {
        for(int j = 1; j <= w; j++)
        {
            map[i][j] = getchar();
        }
        getchar();
    }
 
    while(1)
    {
        char c = getchar();
        if(c == '0' || c == '\n')break;
        else key[c - 'a'= 1;
    }
}
 
int dfs(int x, int y)//0,0
{
    int ret = 0;
 
    visit[x][y] = 1;
 
    if(map[x][y] == '$') ret++;
 
    else if(map[x][y] >= 'a' && map[x][y] <= 'z')
    {
        key[map[x][y] - 'a'= 1;
        flag = 1;
    }
 
 
    for(int i = 0; i < 4; i++)
    {
        int nx = x + dx[i];
        int ny = y + dy[i];
 
        if(nx < 0 || ny < 0 || nx > h + 1|| ny > w + 1continue;
        if(map[nx][ny] == '*'continue;
        if(visit[nx][ny]) continue;
 
        if(map[nx][ny] >= 'A' && map[nx][ny] <= 'Z' && !key[map[nx][ny] - 'A'])
        {
            v.push_back(make_pair(nx, ny));
            continue;
        }
 
        ret += dfs(nx, ny);
    }
 
 
    return ret;
}
 
 
int main()
{
    int t;
    scanf("%d"&t);
    while(t--)
    {
        //초기화 부분
        memset(visit, 0sizeof(visit));
        memset(key, 0sizeof(key));
        memset(map, 0sizeof(map));
        v.clear();
 
        input(); // 입력 부분
 
        int ret = dfs(00); // dfs 첫 탐색
 
        while(1// 와일문을 반복하며 백터를 탐색
        {
            flag = 0;
 
            for(int i = 0; i < v.size(); i++)
            {
                if(key[map[v[i].first][v[i].second] - 'A'])
                    ret += dfs(v[i].first, v[i].second);
            }
 
            if(flag == 0break// 키를 얻은 것이 없다면 탈출
        }
 
        printf("%d\n", ret);
    }
    return 0;
}
cs


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

[5427] 불  (0) 2017.04.16
[13460] 째로탈출2  (2) 2017.04.16
[12100] 2048 easy  (0) 2017.04.16
[5214] 환승  (0) 2017.04.04
[9009] 피보나치  (0) 2017.04.04

시간 제한메모리 제한제출정답맞은 사람정답 비율
1 초128 MB1970111996458.673%

문제

B진법 수 N이 주어진다. 이 수를 10진법으로 바꿔 출력하는 프로그램을 작성하시오.

10진법을 넘어가는 진법은 숫자로 표시할 수 없는 자리가 있다. 이런 경우에는 다음과 같이 알파벳 대문자를 사용한다.

A: 10, B: 11, ..., F: 16, ..., Y: 34, Z: 35

입력

첫째 줄에 N과 B가 주어진다. (2 ≤ B ≤ 36)

B진법 수 N을 10진법으로 바꾸면, 항상 10억보다 작거나 같다.

출력

첫째 줄에 B진법 수 N을 10진법으로 출력한다.

예제 입력 

ZZZZZ 36

예제 출력 

60466175





























간단한게 해결할 수 있는 문제입니다.


만약 문자열이 ABCDEFG라면 G부터 접근하면서 N의 인덱스만큼 제곱을 해주면

끝나는 문제입니다.


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 <cstdio>
#include <iostream>
#define ll long long
 
using namespace std;
 
ll pow(int n, int r)
{
    if(r == 0return 1;
    else if(r % 2return pow(n, r - 1* n;
    else
    {
        ll tmp = pow(n, r / 2);
        return tmp * tmp;
    }
}
 
ll convert(string str, int sys)
{
    ll ret = 0;
    for(int i = str.size() - 1; i >= 0; i--)
    {
        int tmp;
        if(str[i] >= 'A' && str[i] <= 'Z') tmp = str[i] - 'A' + 10;
        else tmp = str[i] - '0';
 
        ret += tmp * pow(sys, str.size() - (i + 1));
    }
    return ret;
}
 
int main()
{
    string str;
    cin>>str;
 
    int system;
    cin>>system;
 
    printf("%lld\n", convert(str,system));
    return 0;
}
 
cs


'알고리즘 > 구현' 카테고리의 다른 글

[5624] 좋은 수  (0) 2017.04.06
[3190] 뱀  (0) 2017.04.05
[1952] 달팽이2  (0) 2017.04.04
[3460] 이진수  (0) 2017.04.02
[2399] 거리의 차이  (2) 2017.04.02


10진수를 입력받아서 bin이라는 배열에 2진수 rev를 저장했습니다.

그리고 인덱스 0부터 접근하여 1인경우 출력했습니다.


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
#include <cstdio>
 
int convert_bin(int dec, bool *bin)
{
    int i = 0;
 
    while(dec)
    {
        bin[i++= dec % 2;
        dec /= 2;
    }
 
    return i;
}
 
int main()
{
    int t;
    scanf("%d"&t);
    while(t--)
    {
        int dec;
        bool bin[21]; // 10^6까지이므로 2^20제곱과 비슷
 
        scanf("%d"&dec);
        int size = convert_bin(dec, bin);
 
        for(int i = 0; i < size; i++) if(bin[i]) printf("%d ", i);
        puts("");
    }
    return 0;
}
 
cs


'알고리즘 > 구현' 카테고리의 다른 글

[5624] 좋은 수  (0) 2017.04.06
[3190] 뱀  (0) 2017.04.05
[1952] 달팽이2  (0) 2017.04.04
[2745] 진법 변환  (0) 2017.04.02
[2399] 거리의 차이  (2) 2017.04.02

+ Recent posts