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


단순 구현 문제입니다.


N이 100이기 때문에 시간복잡도 N^2으로 해결할 수 있습니다.


그냥 한번씩 다 밟아보면서 카운트하고

mod를 이용하여 어떤 색인지 판별하면 되겠습니다.


코드입니다.

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
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <string.h>
using namespace std;
 
#define ll long long
#define MOD (ll)1e15
#define MAX_SIZE (int)1e5
#define mp make_pair
#define INF 987654321
#define pii pair<int, int>
//ios::sync_with_stdio(false); cin.tie(0);
 
int pos[100];
char direct[100];
 
int cnt[101];
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
 
    int p;
    cin >> p;
 
    int n;
    cin >> n;
 
    for (int i = 0; i < n; i++) {
        cin >> pos[i] >> direct[i];
    }
 
    //N^2의 복잡도로 돌 
    for (int i = 0; i < n; i++) {
        int d = (direct[i] == 'L' ? -1 : 1);
 
        for (int j = pos[i] + d; j > 0 && j <= 100; j += d) {
            cnt[j]++;
        }
    }
 
    int b, r, g;
    b = r = g = 0;
    
    //나머지 연산을 이용하여 개수 체킹
    for (int i = 1; i <= 100; i++) {
        int mod = cnt[i] % 3;
        if (mod == 0) b++;
        else if (mod == 1) r++;
        else g++;
    }
 
    //2자리로 고정하기
    cout << fixed;
    cout.precision(2);
    cout << ((double)b / 100) * p << '\n';
    cout << ((double)r / 100) * p << '\n';
    cout << ((double)g / 100) * p << '\n';
 
    return 0;
}
cs


저작자표시

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

[14488] 준오는 급식충이야!  (0) 2017.07.29
[1913] 달팽이  (0) 2017.07.27
[10986] 나머지 합  (0) 2017.07.24
[3474] 교수가 된 현우  (0) 2017.07.13
[5527] 전구 장식  (0) 2017.07.05

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


분류가... https://www.acmicpc.net/problem/tag/Prefix%20Sum


prefix sum??이라고 되어있네요..뭔지 잘모르겠습니당.....


이 문제는 


(a + b) % MOD = (a % MOD + b % MOD) % MOD
라는 것을 이용해야합니다.


a1 + a2 + a3 + ... + an = Sn

이라고 했을 때


aj + a(j+1) + a(j + 2) + ... ai = Si - S(j-1)


입니다.


예제의

5 3
1 2 3 1 2


라고 인풋이 들어오면


2 3 1을 더해도 3으로 나눴을때 나머지가 0이되겠죠??


이것을 어떻게 찾냐???

하면


1 2 3 1 을 다더하면 7이 나오겟죠??


근데 인덱스 0까지의 합은 1입니다.


그렇다면 

인덱스 1~3은 S3 - S0입니다.


S0의 나머지는 1

S3의 나머지 또한 1이죠


그렇다하면 나머지 두개가 같은 이 S3 와 S0을 뺀다면

나머지가 0이됩니다.

즉 이 둘을 뻇을 때 나머지가 0이라는 말입니다.


데이터를 받을 때마다 연속적으로 합을 구해서 mod값으로 나누고 나눈 나머지값들을 각각

카운트합니다.


그리고 m미만의 각 개수에 대해서 n(해당 모드의 개수)C2를 해주면됩니다.(n개 중에 2개를 고르는 방법)


주의할 점은 나머지가 0인경우 nC2 + 자기자신도 이미 나누어지기 때문에 자기자신의 개수까지 더해야한다는 점입니다.


코드입니다.

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
#include <iostream>
#include <vector>
 
using namespace std;
 
#define ll long long
#define MOD (ll)1e15
#define MAX_SIZE (int)1e5
#define mp make_pair
#define INF 987654321
#define pii pair<int, int>
//ios::sync_with_stdio(false); cin.tie(0);
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int n, m;
    cin >> n >> m;
 
    ll sum = 0;
    ll c[1000] = { 0, };
 
    //인풋받으면서 sum에다가 인풋받은값을 계속더해줌
    //그리고 그 합에 대해서 mod를 나눠서 c라는 배열에 카운팅해줌.
    while (n--) {
        int a;
        cin >> a;
        sum += a;
        c[sum % m]++;
    }
 
    ll ret = c[0];//0은 그자체로 이미 나머지가 0이기때문에
    for (int i = 0; i < m; i++) ret += (c[i] * (c[i] - 1)) / 2;//nC2
 
    cout << ret;
 
    return 0;
}
 
cs


저작자표시

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

[1913] 달팽이  (0) 2017.07.27
[14649] 문홍안  (0) 2017.07.27
[3474] 교수가 된 현우  (0) 2017.07.13
[5527] 전구 장식  (0) 2017.07.05
[14499] 주사위 굴리기  (0) 2017.04.16

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


음..

정수론 문제입니다.

0의 개수를 체크하라...


숫자의 뒤에 0이 붙으려면 소인수 분해를 했을 때

2와 5가 있어야합니다.


코드 공개합니다!

(사실 2를 안세고 5만세도되용!!!)

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 <cstdlib>
#include <cmath>
#include <string.h>
#include <queue>
#include <iostream>
#include <algorithm>
#include <vector>
#include <functional>
#include <stack>
#include <string>
 
#define ll long long
#define INF 987654321
#define MOD 10000
#define MAX_SIZE 751
#define mp make_pair
#define pii pair<int, int>
//ios::sync_with_stdio(false); cin.tie(0);
using namespace std;
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
 
        ll cnt2 = 0, cnt5 = 0;
 
        for (int i = 2; i <= n; i *= 2) {
            cnt2 += n / i;
        }
 
        for (int i = 5; i <= n; i *= 5) {
            cnt5 += n / i;
        }
 
        printf("%lld\n", min(cnt2, cnt5));
    }
    return 0;
}
cs


저작자표시

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

[14649] 문홍안  (0) 2017.07.27
[10986] 나머지 합  (0) 2017.07.24
[5527] 전구 장식  (0) 2017.07.05
[14499] 주사위 굴리기  (0) 2017.04.16
[5624] 좋은 수  (0) 2017.04.06

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



처음에 예제를 보고

같은 전구가 반복되는 pos부터

같은 전구가 또 반복되는 pos -1까지 반전시키면 된다고 생각했습니다.


예제의

1 1 0 0 1 0 1 1 1 0

의 예제에서


처음 1 1(pos 0, 1)이 반복됩니다. 

그래서 pos = 1 부터 그 다음에 0 0 이 반복되기 때문에 pos - 1까지의 구간을 반전시키면


1 0 1 0 1 0 1 1 1 0

7이 됩니다.


그 다음 다시 원상 복귀!

1 1 0 0 1 0 1 1 1 0에서

0 0 구간 (위에서 찾은 pos 값 즉.. 3!!!!! 인덱스를 말하는 것)

3부터 시작해서

또 반복되는 구간은

1 1 1

즉 인덱스(pos) 7입니다. 그럼 pos - 1까지 반전을 시켜야하므로

1 1 0 1 0 1 0 1 1 0

7이 됩니다.


마지막으로

1 1 1 구간에서 반복이 연속되므로  1 0 1을 바꿔주는 경우가 있습니다.

1 1 0 0 1 0 1 0 1 0

이것또한 7입니다.


즉 정답은 7입니다!!!!!!!


근데... 이렇게 푸니까 시간 초과..ㅠㅠㅠㅠㅠ


반전시키는 구간 길이가 n이면 n만큼의 시간이 걸릴테고..

구간을 찾는 것도 시간이 걸리고...

여러가지 이유로 시간이 초과됩니다...


n의 시간으로 해결할 수 있어야 할 것 같은데 방법이 잘 떠오르지 않았습니다.


문제의 해결 방법은


전구를 세 구간으로 나누는 것입니다.

이게 무슨 말이냐면


반전 시키는 구간을 O

아닌 구간을 X로 치면


O X X

X O X

X X O

로 구간을 나누면 된다는 말입니다.


구간을 나누는 기준은 같은 전구가 반복되는 pos입니다.


1 1 0 0 1 0 1 1 1 0

이 예제에서는 위에서 설명한 구간이겠지요.


이렇게 해서

배열에 같은 전구가 나올 때 까지의 번갈아가는 패턴의 값을 저장합니다.!


a[0] = 1;(인덱스 0에서 0구간)

a[1] = 2;(인덱스 1에서 2구간)

a[2] = 4;(인덱스 3에서 6구간)

a[3] = 1;(인덱스 7에서 7구간)

a[4] = 2;(인덱스 8에서 9구간)


이렇게 다섯개의 구간이 생성됩니다.


이 5개의 구간 중 연속된 3개를 더하면 최대 번갈아가는 패턴의 값이 나오겠지요!


아래는 정답 코드입니다.

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 <cstdio>
#include <cstdlib>
#include <cmath>
#include <string.h>
#include <queue>
#include <iostream>
#include <algorithm>
#include <vector>
#include <functional>
#include <stack>
 
#define ll long long
#define INF 987654321
#define MOD 1000000
#define MAX_SIZE 100000
 
using namespace std;
 
int a[MAX_SIZE];
int n;
 
int main() {
 
    scanf("%d", &n);
 
    int before = -1;
    int pos = 1;
 
    for (int i = 0; i < n; i++) {
        int t;
        scanf("%d", &t);
        
        if (before == t) pos++;
        
        a[pos]++;
        before = t;
    }
 
    int ret = 0;
    for (int i = 1; i <= pos; i++) {
        ret = max(ret, a[i - 1] + a[i] + a[i + 1]);
    }
 
    printf("%d", ret);
 
    return 0;
}
 
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
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <string.h>
#include <queue>
#include <iostream>
#include <algorithm>
#include <vector>
#include <functional>
#include <stack>
 
#define ll long long
#define INF 987654321
#define MOD 1000000
#define MAX_SIZE 100000
 
using namespace std;
 
bool a[MAX_SIZE];
int n;
 
int cnt(int start, int end) {
    int before = -1;
    int ret = 0;
    int tmp = 0;
 
    bool flag = 0;
    for (int i = 0; i < n; i++) {
        if (start <= i && i <= end) {
            a[i] = !a[i];
            flag = 1;
        }
        if (before != a[i]) tmp++;
        else ret = max(ret, tmp), tmp = 1;
 
        before = a[i];
 
        if (flag) {
            flag = 0;
            a[i] = !a[i];
        }
    }
 
    return ret;
}
 
int f(int pos, int before) {
    int i;
 
    for (i = pos + 1; i < n; i++) {
        if (before == a[i]) {
            break;
        }
 
        before = a[i];
    }
 
    return cnt(pos, i - 1);
}
 
int main() {
    
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++) scanf("%d", a + i);
    
    int before = -1;
    int ret = cnt(-1, -1);
 
    for (int i = 0; i < n; i++) {
        if (before == a[i]) {
            ret = max(ret, f(i, a[i]));
        }
 
        before = a[i];
    }
 
    printf("%d", ret);
 
    return 0;
}
cs


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

[10986] 나머지 합  (0) 2017.07.24
[3474] 교수가 된 현우  (0) 2017.07.13
[14499] 주사위 굴리기  (0) 2017.04.16
[5624] 좋은 수  (0) 2017.04.06
[3190] 뱀  (0) 2017.04.05


이 문제는 난이도가 굉장히 낮은데..

주사위를 굴렸을 때.. 전개도에서 인덱스만 잘 스왑해주면 끝나는 문제입니다.

핵심 함수는 dice_move()입니다.



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
#include <stdio.h>
#include <iostream>
 
#define MAX_SIZE 25
 
using namespace std;
 
int m, n;
int sx, sy;
int k;
int map[MAX_SIZE][MAX_SIZE];
int cmd[1000];
int dx[4] = { 0, 0, -1, 1 };//동서북남
int dy[4] = { 1, -1, 0, 0 };
int dice[6] = {0, };
 
void dice_move(int d){
    switch (d){
    case 0://동
        swap(dice[2], dice[0]);
        swap(dice[0], dice[3]);
        swap(dice[3], dice[5]);
        break;
    case 1://서
        swap(dice[3], dice[0]);
        swap(dice[0], dice[2]);
        swap(dice[2], dice[5]);
        break;
    case 2://북
        swap(dice[4], dice[5]);
        swap(dice[0], dice[4]);
        swap(dice[1], dice[0]);
        break;
    case 3://남
        swap(dice[1], dice[0]);
        swap(dice[0], dice[4]);
        swap(dice[4], dice[5]);
        break;
    }
 
}
 
void input(){
    scanf("%d %d", &m, &n);
    scanf("%d %d", &sx, &sy);
    scanf("%d", &k);
    for (int i = 0; i < m; i++){
        for (int j = 0; j < n; j++){
            scanf("%d", &map[i][j]);
        }
    }
 
    for (int i = 0; i < k; i++){
        int d;
        scanf("%d", &d);
        cmd[i] = d - 1;
    }
 
}
 
void solve(){
    int x = sx;
    int y = sy;
 
    for (int i = 0; i < k; i++){
        int nx = x + dx[cmd[i]];
        int ny = y + dy[cmd[i]];
 
        if (nx < 0 || ny < 0 || nx >= m || ny >= n) continue;
        
        dice_move(cmd[i]);//아래는 5번인덱스; 위는 0
 
        if (map[nx][ny] == 0){
            map[nx][ny] = dice[5];
        }
        else{
            dice[5] = map[nx][ny];
            map[nx][ny] = 0;
        }
        printf("%d\n", dice[0]);
 
        x = nx;
        y = ny;
    }
 
 
}
 
int main(){
    input();
    solve();
 
 
    return 0;
    
}
cs


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

[3474] 교수가 된 현우  (0) 2017.07.13
[5527] 전구 장식  (0) 2017.07.05
[5624] 좋은 수  (0) 2017.04.06
[3190] 뱀  (0) 2017.04.05
[1952] 달팽이2  (0) 2017.04.04

좋은 수 성공

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

문제

정수 N개로 이루어진 수열 A가 있다. 이 때, i번째 수가 그 앞에 있는 수 세 개의 합으로 나타낼 수 있을 때, 그 수를 좋다고 한다. (같은 위치에 있는 수를 여러번 더해도 된다)

수열이 주어졌을 때, 총 몇 개의 수가 좋은 수 일까?

입력

첫째 줄에 수열 A의 크기 N이 주어진다. (1 ≤ N ≤ 5000) 둘째 줄에는 수열 A의 각 숫자가 공백으로 구분되어 주어진다. (-100,000 ≤ Ai ≤ 100,000)

출력

첫째 줄에 좋은 수의 개수를 출력한다.

예제 입력 

6
1 2 3 5 7 10

예제 출력 

4

힌트












이 문제는 A + B + C = D를 찾는 문제입니다.

그렇다고 N^3을 하기에는 N이 5000까지입니다.

 

이 문제의 포인트는 2가지입니다.

 

1.  A + B = D - C 로 식을 변형한다.

2. Ai의 범위가 -10^5 ~ 10^5라는 점.


풀이 방법은 1번과 2번을 이용하면 A + B의 범위가 -2 * 10 ^5 ~ 2 * 10^5라는 것을 알 수 있습니다.저게 핵심입니다. 

저만큼의 배열을 선언해서 0부터 20만까지는 -범위 20만부터 40만까지는 + 범위입니다.

이제부터 두가지 풀이법에 대해서 설명해드리겠습니다.


1번 풀이는 i포문을 돌 때 해당 i 전까지 if(ab[data[i] - data[j] + MAX_VALUE])가 존재하는 지 검사한다.

이 말은 d - c가 존재하는지 검사합니다.

그리고 존재하면 좋은 수이므로 ret을 증가시킵니다.

 

for(int j = 0; j <= i; j++) ab[data[i] + data[j] + MAX_VALUE] = 1;

이 코드는 a+b를 존재한다고 표시해줍니다. 이 과정을 반복합니다.

 

아래의 코드입니다.

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
#include <cstdio>
#include <string.h>
 
#define MAX_SIZE 5000
#define MAX_VALUE 200000
 
int data[MAX_SIZE];
bool ab[MAX_VALUE * 2];
 
int main()
{
 
    int n;
    scanf("%d", &n);
 
    for(int i = 0; i < n; i++) scanf("%d", data + i);
 
 
    int ret = 0;
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < i; j++)
        {
            if(ab[data[i] - data[j] + MAX_VALUE])
            {
                ret++;
                break;
            }
        }
 
        for(int j = 0; j <= i; j++) ab[data[i] + data[j] + MAX_VALUE] = 1;
    }
 
    printf("%d\n", ret);
 
    return 0;
}
 
cs



아래는 2번 풀이입니다.

이 풀이는 가능한 a+b를 테이블에 다 저장합니다.

위의 풀이와 다른점은 인덱스를 저장한다는 점입니다.

a+b가 검사하는 d 이후에 만들어졌다면 사용할 수 없는 a + b이기 때문입니다.

 

if(tmp != -1 && tmp < i)를 이용해서 -1이면 a + b = d - c 를 만족하지 않으므로 좋은 수가 아니고

tmp >= i 라면 나의 인덱스보다 이후에 만들어진 수이므로 좋은 수가 아닙니다.


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
#include <cstdio>
#include <string.h>
 
#define MAX_SIZE 5000
#define MAX_TABLE 400002
 
int n;
int data[MAX_SIZE];
int table[MAX_TABLE];
 
int main()
{
    memset(table, -1, sizeof(table));
 
    scanf("%d", &n);
    for(int i = 0; i < n; i++) scanf("%d", data + i);
 
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j <= i; j++)
        {
            int sum = data[i] + data[j];
            int& tmp = table[200000 + sum];
            if(tmp == -1) tmp = i;
        }
    }
 
    int ret = 0;
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < i; j++)
        {
            int diff = data[i] - data[j];
            int& tmp = table[200000 + diff];
            if(tmp != -1 && tmp < i)
            {
                ret++;
                break;
            }
        }
    }
 
    printf("%d\n", ret);
    return 0;
}
 
cs


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

[5527] 전구 장식  (0) 2017.07.05
[14499] 주사위 굴리기  (0) 2017.04.16
[3190] 뱀  (0) 2017.04.05
[1952] 달팽이2  (0) 2017.04.04
[2745] 진법 변환  (0) 2017.04.02

뱀 성공

시간 제한메모리 제한제출정답맞은 사람정답 비율
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] == 1) break;
        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<int, int> p;
 
int N, K, L;
int map[MAX_SIZE][MAX_SIZE]; // 사과는 2, 뱀은 1, 맵은 0
vector<p> v; //sec, turn
 
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
 
//오른쪽 : 위 -> 오, 아래 -> 왼, 오 -> 아, 왼 -> 위
//왼쪽 : 위 -> 왼, 아래 -> 오른, 오 -> 위, 왼 -> 아
 
//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 == 1) return (now + 2) % 4;
        else return 3 - now;
    }
    else // 오른쪽
    {
        if(now == 0 || now == 1) return 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] == 1) break;
        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 성공

시간 제한메모리 제한제출정답맞은 사람정답 비율
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] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
//3 -> 1, 1 -> 2, 2 -> 0, 0 -> 3
//오 -> 아, 아 -> 왼, 왼 -> 위 , 위 -> 오
 
int set_direct(int d)
{
    if(d == 3 || d == 2) return (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] == 1) break;
 
        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

+ Recent posts

티스토리툴바