<링크>

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


<소스코드>

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;
int pan[101][101];
void check(int x, int y, int d, int g)
{
    vector<int> v;
    v.push_back(d);
    for (int i = 0; i < g; ++i)
    {
        int size = v.size();
        for (int j = size - 1; j >= 0; --j)
        {
            int dir = v[j];
            int toDir = (dir + 1) % 4;
            v.push_back(toDir);
        }
    }
    int size = v.size();
    pan[x][y] = 1;
 
    for (int i = 0; i < size; ++i)
    {
 
        int dir = v[i];
        switch (dir)
        {
        case 0:++x; break;
        case 1:--y; break;
        case 2:--x; break;
        case 3:++y; break;
        }
        pan[x][y] = 1;
    }
}
int main()
{
    int N;
    scanf("%d", &N);
    while (N--)
    {
        int x, y, d, g;
        scanf("%d%d%d%d", &x, &y, &d, &g);
        check(x, y, d, g);
    }
    int ans = 0;
    for (int x = 0; x<100; ++x)
        for (int y = 0; y <100; ++y)
        {
            if (pan[x][y] && pan[x + 1][y] && pan[x][y + 1] && pan[x + 1][y + 1])
                ++ans;
        }
    printf("%d", ans);
}
 
cs


<풀이>

그림처럼 이전세대의 선분 하나랑 다음세대의 선분 한쌍이 각각 관계가 있다.


시작점부터의 방향만을 리스트로 나타내면 다음과 같다. 

잘 보면 규칙성을 발견할 수 있다. 

기존 세대의 방향 맨 끝부터 봤을때 기존 방향에서 왼쪽으로 90' 꺾은 방향으로 다음세대의 방향이 결정된다.

①↑에서 ←

②←에서↓

③↑에서 ←

④→에서↑

이런 규칙으로 변한다. 근데 문제에서도 친절하게


  • 0: x좌표가 증가하는 방향 (→)
  • 1: y좌표가 감소하는 방향 (↑)
  • 2: x좌표가 감소하는 방향 (←)
  • 3: y좌표가 증가하는 방향 (↓)

라고 되어있기 때문에 다음방향 = (이전방향+1)%4 이 된다.

이런식으로 K세대까지의 방향만을 쫙 만들어놓은 후

시작점부터 해당좌표에 체크해준다.


저작자표시

'알고리즘 풀이 > 시뮬레이션' 카테고리의 다른 글

백준 14890 경사로 :: 들짐승  (0) 2018.07.22
백준 14499 주사위굴리기 :: 들짐승  (0) 2018.07.22
백준 3190 뱀 :: 들짐승  (0) 2018.07.22
백준 12100 2048(Easy) :: 들짐승  (0) 2018.07.22

<링크>

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


<풀이>

시키는 대로 하면된다.
문제에 나와있는 조건을 구현하는데
모든 행을 쭉 봐야하고 모든 열을 또 봐야하기 때문에 처음부터 2차원 배열을 두 개를 만들었다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
for(int i=0;i<N;++i)
        for (int j = 0; j < N; ++j)
        {
            int n;
            scanf("%d", &n);
            h[i][j] = v[j][i] = n;
        }
 
.....
 
 
for (int i = 0; i < N; ++i)
    {
        ans += isValid(h[i]);
        ans += isValid(v[i]);
    }
cs

가로방향, 세로방향을 한번에 입력해놓고 각 행의 주소를 포인터 인자로 넘겨줘서 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
#include<stdio.h>
int h[100][100];
int v[100][100];
int N, L;
int isValid(int *);
int main()
{
    scanf("%d%d", &N, &L);
    for(int i=0;i<N;++i)
        for (int j = 0; j < N; ++j)
        {
            int n;
            scanf("%d", &n);
            h[i][j] = v[j][i] = n;
        }
    
    int ans = 0;
    for (int i = 0; i < N; ++i)
    {
        ans += isValid(h[i]);
        ans += isValid(v[i]);
    }
    printf("%d", ans);
}
int isValid(int *p)
{
    int installed[100] = { 0, };
    for (int i = 1; i < N; ++i)
    {
        if (p[i - 1] < p[i])
        {
            if (i - L < 0)
                return 0;
            int height = p[i]-1;
            for (int j = i - 1; j >= i - L; --j)
                if (height != p[j] || installed[j]) 
                    return 0;
            for (int j = i - 1; j >= i - L; --j)
                installed[j] = 1;
        }
        else if (p[i - 1] > p[i])
        {
            if (i + L-1>= N)
                return 0;
            int height = p[i - 1]-1;
            for (int j = i; j < i + L; ++j)
                if (height != p[j] || installed[j])
                    return 0;
            for (int j = i; j < i + L; ++j)
                installed[j] = 1;
 
        }
    }
    return 1;
}
cs


저작자표시

'알고리즘 풀이 > 시뮬레이션' 카테고리의 다른 글

백준 15685 드래곤커브  (0) 2018.09.30
백준 14499 주사위굴리기 :: 들짐승  (0) 2018.07.22
백준 3190 뱀 :: 들짐승  (0) 2018.07.22
백준 12100 2048(Easy) :: 들짐승  (0) 2018.07.22

<링크>

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


<풀이>

주사위를 하나 그려놓고 상하좌우로 굴려보며 규칙성을 찾았다.

주사위 평면도가 다음과 같으면
2면 : 배열[0]
4면 : 배열[1]
1면 : 배열[2]
3면 : 배열[3]
5면 : 배열[4]
6면 : 배열[5]
각각 면의 숫자를 배열 해당위치에 넣어준다. 처음엔 모두 0이다.
위로 굴리면 그림처럼 아랫방향으로 shift되고 4면 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
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
#include<stdio.h>
int dice[6] = { 0,0,0,0,0,0 };
int pan[20][20];
int N, M, x, y, K;
void east();
void west();
void north();
void south();
void check();
int main()
{
    scanf("%d%d%d%d%d", &N, &M,&x,&y,&K);
    for(int i=0;i<N;++i)
        for(int j=0;j<M;++j)
            scanf("%d", &pan[i][j]);
    while (K--)
    {
        int k;
        scanf("%d", &k);
        switch (k)
        {
        case 1:
            if (y + 1 < M)
            {
                east();
                ++y;
                check();
            }
            break;
        case 2:
            if (y - 1 >= 0)
            {
                west();
                --y;
                check();
            }
            break;
        case 3:
            if (x - 1 >= 0)
            {
                north();
                --x;
                check();
            }
            break;
        case 4:
            if (x + 1 < N)
            {
                south();
                ++x;
                check();
            }
            break;
        }
    }
}
void check()
{
    
    if (pan[x][y] == 0)
        pan[x][y] = dice[2];
    else
    {
        dice[2] = pan[x][y];
        pan[x][y] = 0;
    }
    printf("%d\n", dice[5]);
}
void east()
{
    int tmp = dice[1];
    dice[1] = dice[2];
    dice[2] = dice[3];
    dice[3] = dice[5];
    dice[5] = tmp;
}
void west()
{
    int tmp = dice[3];
    dice[3] = dice[2];
    dice[2] = dice[1];
    dice[1] = dice[5];
    dice[5] = tmp;
}
void south()
{
    int tmp = dice[0];
    dice[0] = dice[2];
    dice[2] = dice[4];
    dice[4] = dice[5];
    dice[5] = tmp;
}
void north()
{
    int tmp = dice[5];
    dice[5] = dice[4];
    dice[4] = dice[2];
    dice[2] = dice[0];
    dice[0] = tmp;
}
 
cs


저작자표시

'알고리즘 풀이 > 시뮬레이션' 카테고리의 다른 글

백준 15685 드래곤커브  (0) 2018.09.30
백준 14890 경사로 :: 들짐승  (0) 2018.07.22
백준 3190 뱀 :: 들짐승  (0) 2018.07.22
백준 12100 2048(Easy) :: 들짐승  (0) 2018.07.22

<링크>

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


<풀이>

-body배열 : body[i][j] = 좌표(i,j)가 내 몸이면 1, 아니면 0

//초기에는 사과의 위치로도 쓰인다. 

-comm배열 : comm[i]=j일 때, j는 i초때 전환하는 방향이다.

-toDir배열 : toDir[i][j] = 꼬리가 좌표(i,j)에 있을 때 이동해야한다면 어느방향으로 가야하는가

0. 머리좌표랑 꼬리좌표 다 (1,1)로 초기화 , body[1][1]=1 체크


1. toDir의 머리좌표에 어느방향으로 떠나는지 기록해놓는다. 나중에 해당좌표에서 꼬리를 옮길 때  머리가 떠난 방향 그대로 옮겨야 하기 때문.


2. 방향 대로 머리를 옮기고 시간을 증가시켜준다.


3. 머리가 간 곳이 벽이거나, body배열을 체크했을 때 해당 좌표가 1이면 상태면 프로그램끝.


4. 머리 좌표에 사과가 없으면 body의 꼬리좌표를 0으로 만들어주고, 꼬리를 옮긴다. 옮길 때 아까 적어두었던 toDir배열 참조해서 그 방향 그대로 옮긴다.


5. body배열의 머리 좌표를 1로 갱신


6. 현재 시간에 방향 전환명령이 있으면 방향 갱신

1~6을 반복하면 된다.


<소스코드>

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
#include<stdio.h>
int toDir[101][101]; //나중에 꼬리가 옮겨야할 방향기록
int body[101][101]; //몸이 어느곳을 차지하고있는지
int toI[4] = { 0,-1,0,1 }; //좌상우하
int toJ[4] = { -1,0,1,0 };
char comm[100000];
int main()
{
    int N, K, L;
    scanf("%d%d", &N, &K);
    int a, b;
    while (K--)
    {
        scanf("%d%d", &a, &b);
        body[a][b] = 2;
    }
    scanf("%d", &L);
    while (L--)
    {
        char c;
        scanf("%d%c%c", &a, &c, &c);
        comm[a] = c;
    }
 
    int sec = 0;
 
    int hi, hj, ti, tj;
    hi = hj = ti = tj = 1;
 
    body[hi][hj] = 1;
 
    int dir = 2;
    while (1)
    {
        ++sec;
        toDir[hi][hj] = dir;
        hi += toI[dir];
        hj += toJ[dir];
        if (hi == 0 || hi == N + 1 || hj == 0 || hj == N + 1 || body[hi][hj] == 1)
            break;
        if (body[hi][hj] != 2) //사과 없으면
        {
            body[ti][tj] = 0;
            int d = toDir[ti][tj];
            ti += toI[d];
            tj += toJ[d];
        }
        body[hi][hj] = 1;
        if (comm[sec] != 0)
        {
            if (comm[sec] == 'L')
            {
                if (dir == 0)
                    dir = 3;
                else
                    dir -= 1;
            }
            else
                dir = (dir + 1) % 4;
        }
 
    }
    printf("%d", sec);
}
cs


저작자표시

'알고리즘 풀이 > 시뮬레이션' 카테고리의 다른 글

백준 15685 드래곤커브  (0) 2018.09.30
백준 14890 경사로 :: 들짐승  (0) 2018.07.22
백준 14499 주사위굴리기 :: 들짐승  (0) 2018.07.22
백준 12100 2048(Easy) :: 들짐승  (0) 2018.07.22

<링크>

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


<풀이>

시키는 대로 하면된다.

1.큰그림


재귀로 풀었는데
판때기 상태를 나타내는 2차원 배열을 인자로 받아서

4가지방향(상하좌우)로 이동시킨 모습으로 수정하고
그대로 재귀호출로 넘겨주는 방식이다.


'상' 방향으로 배열을 수정할 때 인자로 받은 배열은 call by reference이기 때문에 그대로 수정하면 맨위에있는 배열이 바뀌게 되고, 다른 방향들을 볼 때 전혀 다른 결과가 되기 때문에

함수가 호출될 때마다 인자로 넘어온 배열을 복사해서 진행했다. 
그럼 각 함수 호출마다 20*20 int배열이 필요하게 된다. 재귀호출된 depth가 깊어질 수록 메모리 사용이 커지는데   배열로만 스택에 4^depth * 400 * sizeof(int)  byte만큼의 메모리를 쓰게 된다. 
문제에 최대 5회라고 되어있으니깐 충분할 것 같아서 진행했다.

2. 각 방향으로 이동할 때

2중 for문을 돌면서 모두 체크한다.
0이 아닌 숫자가 뜨면, 내가 가는 방향으로 바로 다음 칸이 0일 때까지 쭉 간다.
그 후 다음 칸의 숫자랑 나랑 같으면 더해서 다음 칸의 숫자를 만들고 나는 0으로 없애버린다.
이 때, 한 번의 이동에서 두 번이상 더해질 수 없으므로 해당 칸의 숫자가 변했는지 체크하기 위한 배열을 또 만들었다. 이 때문에 메모리 사용이 2배로 더 늘어났을 것이다.

3. 코드를 줄이기 위한 나의 최선


똑같은 수가 세 개가 있는 경우에는 이동하려고 하는 쪽의 칸이 먼저 합쳐지기 때문에 각 방향마다 
2중 for문으로 탐색하는 순서가 달라야 한다.
상, 좌 방향은 판의 왼쪽위부터 우리가 평소하는 2중for문 순서대로 훑으면 되고
우, 하 방향은 판의 오른쪽 아래부터 반대로 훑어야한다.
toI,toJ[4]배열을 만들었다.


<소스코드>

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
#include<stdio.h>
int pan[20][20];
int N;
int toI[4] = { -1,1,0,0 }; //상하좌우
int toJ[4] = { 0,0,-1,1 };
int ans;
void dfs(int(*)[20], int);
void progress1(int(*)[20], int, int);
void progress2(int(*)[20], int, int);
void arrCpy(int(*)[20], int(*)[20]);
int main()
{
    scanf("%d", &N);
 
    for (int i = 0; i < N; ++i) //상,좌
        for (int j = 0; j < N; ++j) {
            scanf("%d", &pan[i][j]);
            if (pan[i][j] > ans)
                ans = pan[i][j];
        }
    dfs(pan, 0);
    printf("%d", ans);
}
void dfs(int(*p)[20], int depth)
{
    if (depth == 5)
        return;
    for (int k = 0; k < 4; ++k)
    {
        int tmpArr[20][20] = { 0, };
        arrCpy(tmpArr, p);
        if (k % 2 == 0)
            progress1(tmpArr, toI[k], toJ[k]);
        else
            progress2(tmpArr, toI[k], toJ[k]);
        dfs(tmpArr, depth + 1);
    }
    return;
}
void progress1(int(*a)[20], int toi, int toj) //상,좌
{
    int check[20][20] = { 0, }; //한번 합쳐진 좌표인지 확인용
    for (int i = 0; i < N; ++i) //상,좌
        for (int j = 0; j < N; ++j)
            if (a[i][j] != 0)
            {
                int curi = i;
                int curj = j;
                int tmp = a[curi][curj];
                while (curi + toi >= 0 && curj + toj >= 0 && a[curi + toi][curj + toj] == 0)
                {
                    a[curi][curj] = 0;
                    curi += toi;
                    curj += toj;
                }
                a[curi][curj] = tmp;
                if (curi + toi >= 0 && curj + toj >= 0
                    && a[curi + toi][curj + toj] == a[curi][curj]
                    &&!check[curi+toi][curj+toj])
                {
                    int sum = a[curi + toi][curj + toj] + a[curi][curj];
                    if (sum > ans)
                        ans = sum;
                    a[curi + toi][curj + toj] = sum;
                    check[curi + toi][curj + toj] = 1;
                    a[curi][curj] = 0;
                }
 
            }
 
 
}
void progress2(int(*a)[20], int toi, int toj) //우,하
{
    int check[20][20] = { 0, }; //한번 합쳐진 좌표인지 확인용
    for (int i = N - 1; i >= 0; --i) //우,하
        for (int j = N - 1; j >= 0; --j)
            if (a[i][j] != 0)
            {
                int curi = i;
                int curj = j;
                int tmp = a[curi][curj];
                
                while (curi + toi <N && curj + toj < N && a[curi + toi][curj + toj] == 0)
                {
                    a[curi][curj] = 0;
                    curi += toi;
                    curj += toj;
                }
                a[curi][curj] = tmp;
                if (curi + toi <N && curj + toj<N
                    && a[curi + toi][curj + toj] == a[curi][curj]
                    && !check[curi + toi][curj + toj])
                {
                    int sum = a[curi + toi][curj + toj] + a[curi][curj];
                    if (sum > ans)
                        ans = sum;
                    a[curi + toi][curj + toj] = sum;
                    check[curi + toi][curj + toj] = 1;
                    a[curi][curj] = 0;
                }
 
            }
}
void arrCpy(int(*a)[20], int(*b)[20])
{
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j)
            a[i][j] = b[i][j];
}
cs


저작자표시

'알고리즘 풀이 > 시뮬레이션' 카테고리의 다른 글

백준 15685 드래곤커브  (0) 2018.09.30
백준 14890 경사로 :: 들짐승  (0) 2018.07.22
백준 14499 주사위굴리기 :: 들짐승  (0) 2018.07.22
백준 3190 뱀 :: 들짐승  (0) 2018.07.22

+ Recent posts

티스토리툴바