문제링크

 

 

15662번: 톱니바퀴 (2)

총 8개의 톱니를 가지고 있는 톱니바퀴 T개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴가 1번, 그 오른쪽은 2번, ..., 가장 오른쪽 톱니바퀴는 T번이다. 아래 그림은 T가 4인 경우이다. 이때, 톱니바퀴를 총 K번 회전시키려고 한다. 톱니바퀴의 회전은 한 칸을 기준으로 한다. 회전은 시계 방향과 반시계 방향이 있고, 아래 그림과 같이 회전한다

www.acmicpc.net

알고리즘 분류

 

시뮬레이션

 

풀이

 

백준 14891 톱니바퀴와 같은 유형의 문제로 이번 문제에선 톱니바퀴의 갯수가 정해져 있지 않다.

풀이 방법은 동일하다. 위의 태그를 참조.

 

코드

 

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
#include <iostream>
#include <string.h>
 
using namespace std;
 
int gear[1001][8];
bool check[1001];
int T;
 
void spin(int n, int d)
{
    check[n] = true;
 
    if (T != 1)
    {
        if (n == 1) // 왼쪽 끝 톱니바퀴
        {
            if (!check[2])
            {
                if (gear[1][2] != gear[2][6])
                    spin(2, -d);
            }
        }
        else if (n == T) // 오른쪽 끝 톱니바퀴
        {
            if (!check[T - 1])
            {
                if (gear[T - 1][2] != gear[T][6])
                    spin(T - 1, -d);
            }
        }
        else
        {
            if (!check[n - 1])
            {
                if (gear[n - 1][2] != gear[n][6])
                    spin(n - 1, -d);
            }
            if (!check[n + 1])
            {
                if (gear[n][2] != gear[n + 1][6])
                    spin(n + 1, -d);
            }
        }
    }
 
    if (d == 1) // 시계 방향 회전
    {
        int temp = gear[n][7];
 
        for (int i = 7; i >= 1; i--)
        {
            gear[n][i] = gear[n][i - 1];
        }
        gear[n][0] = temp;
    }
 
    if (d == -1) // 반 시계 방향 회전
    {
        int temp = gear[n][0];
 
        for (int i = 0; i < 7; i++)
        {
            gear[n][i] = gear[n][i + 1];
        }
        gear[n][7] = temp;
    }
}
int main()
{
    //freopen("input.txt", "r", stdin);
    //setbuf(stdout, NULL);
 
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> T;
    for (int i = 1; i <= T; i++)
    {
        for (int j = 0; j < 8; j++)
        {
            scanf(" %1d", &gear[i][j]);
        }
    }
 
    int k;
 
    cin >> k;
 
    for (int i = 0; i < k; i++)
    {
        memset(check, 0, sizeof(check));
        int a, b;
        cin >> a >> b;
 
        spin(a, b);
    }
 
    int ans = 0;
    for (int i = 1; i <= T; i++)
    {
        if (gear[i][0] == 1)
        {
            ans++;
        }
    }
    printf("%d", ans);
}

'Algorithm > boj' 카테고리의 다른 글

백준 2110번 공유기 설치  (1) 2021.10.24
백준 14890번 경사로  (0) 2019.11.11
백준 14503 로봇 청소기  (0) 2019.11.11
백준 14891번 톱니바퀴  (0) 2019.11.10
백준 14499번 주사위 굴리기  (0) 2019.11.10
 

문제 링크

 

 

14891번: 톱니바퀴

총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴가 1번, 그 오른쪽은 2번, 그 오른쪽은 3번, 가장 오른쪽 톱니바퀴는 4번이다. 이때, 톱니바퀴를 총 K번 회전시키려고 한다. 톱니바퀴의 회전은 한 칸을 기준으로 한다. 회전은 시계 방향과 반시계 방향이 있고, 아래 그림과 같이 회전한다. 톱니바퀴를 회전시키려

www.acmicpc.net

 

알고리즘 분류

 

시뮬레이션

 

풀이

 

맞닿은 극이 서로 다른 경우의 회전을 하게 되는 경우 맞닿은 톱니바퀴에서 다시 회전이 일어나게 되는데 재귀함수를 통해 문제를 해결했습니다.

톱니바퀴를 왼쪽 끝, 오른쪽 끝, 나머지 세 가지의 경우로 나누어 함수를 설계하였고, 맞닿은 부분이 서로 다른 극일 때 회전 방향을 반대로 하여 재귀호출 해주었습니다. 이미 회전이 일어난 톱니바퀴가 다시 호출되는 일을 막기 위해

check배열을 사용하여 이미 회전이 일어난 톱니바퀴를 체크해주었습니다.

 

코드

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
#include <iostream>
#include <string.h>
 
using namespace std;
 
int gear[5][8];
bool check[5];
int T;
 
void spin(int n, int d)
{
    check[n] = true;
 
    if (T != 1)
    {
        if (n == 1) // 왼쪽 끝 톱니바퀴
        {
            if (!check[2]) // 오른쪽의 톱니만 검사
            {
                if (gear[1][2] != gear[2][6])
                    spin(2, -d);
            }
        }
        else if (n == T) // 오른쪽 끝 톱니바퀴
        {
            if (!check[T - 1]) // 왼쪽의 톱니만 검사
            {
                if (gear[T - 1][2] != gear[T][6])
                    spin(T - 1, -d);
            }
        }
        else // 중간 톱니바퀴들
        {
            if (!check[n - 1])
            {
                if (gear[n - 1][2] != gear[n][6])
                    spin(n - 1, -d);
            }
            if (!check[n + 1])
            {
                if (gear[n][2] != gear[n + 1][6])
                    spin(n + 1, -d);
            }
        }
    }
 
    if (d == 1) // 시계 방향
    {
        int temp = gear[n][7];
 
        for (int i = 7; i >= 1; i--)
        {
            gear[n][i] = gear[n][i - 1];
        }
        gear[n][0] = temp;
    }
 
    if (d == -1) // 반시계 방향
    {
        int temp = gear[n][0];
 
        for (int i = 0; i < 7; i++)
        {
            gear[n][i] = gear[n][i + 1];
        }
        gear[n][7] = temp;
    }
}
int main()
{
    //freopen("input.txt", "r", stdin);
    //setbuf(stdout, NULL);
 
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    T = 4; // 톱니바퀴 4개
 
    for (int i = 1; i <= T; i++)
    {
        for (int j = 0; j < 8; j++)
        {
            scanf(" %1d", &gear[i][j]);
        }
    }
 
    int k;
 
    cin >> k;
 
    for (int i = 0; i < k; i++)
    {
        memset(check, 0, sizeof(check));
        int a, b;
        cin >> a >> b;
 
        spin(a, b);
    }
 
    int ans = 0;
    for (int i = 1; i <= T; i++)
    {
        if (gear[i][0] == 1)
        {
            ans++;
        }
    }
    printf("%d", ans);
}

'Algorithm > boj' 카테고리의 다른 글

백준 2110번 공유기 설치  (1) 2021.10.24
백준 14890번 경사로  (0) 2019.11.11
백준 14503 로봇 청소기  (0) 2019.11.11
백준 15662번 톱니바퀴 (2)  (0) 2019.11.10
백준 14499번 주사위 굴리기  (0) 2019.11.10

 

문제 링크

 

14499번: 주사위 굴리기

첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지도에 쓰여 있는 수가 북쪽부터 남쪽으로, 각 줄은 서쪽부터 동쪽 순서대로 주어진다. 주사위를 놓은 칸에 쓰여 있는 수는 항상 0이다. 지도의 각 칸에 쓰여 있는 수는 10을 넘지 않는 자연수 또는 0이다. 마

www.acmicpc.net

알고리즘 분류

 

시뮬레이션

 

풀이

 

문제에 나와있는 모든 조건을 구현해야 하는 시뮬레이션 문제입니다.

동,서,남,북 이동 방향에 따라 주사위의 면을 옮겨주는 함수를 구현하고,

조건에 맞춰 이동한 칸에 수가 있을 때와 없을 때의 조건을 구현해주면 됩니다.

 

코드

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
#include <iostream>
 
using namespace std;
 
int dy[5] = { 0,0,0,-1,1 };
int dx[5] = { 0,1,-1,0,0 };
int n, m, sy, sx , k;
int map[21][21];
int d[7],cd[7];
 
void dmove(int dir)
{
    for (int i = 1; i <= 6; i++)
        cd[i] = d[i];
    
    int ny, nx;
 
    ny = sy + dy[dir];
    nx = sx + dx[dir];
    
    if (ny < 0 || nx < 0 || ny >= n || nx >= m)
        return;
 
    sy = ny;
    sx = nx;
    
    if (dir == 1) // 동쪽
    {
        d[3] = cd[6];
        d[1] = cd[3];
        d[4] = cd[1];
        d[6] = cd[4];
        d[2] = cd[2];
        d[5] = cd[5];
    }
    if (dir == 2) // 서쪽
    {
        d[1] = cd[4];
        d[3] = cd[1];
        d[6] = cd[3];
        d[4] = cd[6];
        d[5] = cd[5];
        d[2] = cd[2];
    }
    if (dir == 3) // 북쪽
    {
        d[1] = cd[2];
        d[2] = cd[6];
        d[6] = cd[5];
        d[5] = cd[1];
        d[3] = cd[3];
        d[4] = cd[4];
    }
    if (dir == 4) // 남쪽
    {
        d[1] = cd[5];
        d[5] = cd[6];
        d[6] = cd[2];
        d[2] = cd[1];
        d[3] = cd[3];
        d[4] = cd[4];
    }
 
    if (map[ny][nx] == 0) // 이동한 칸에 쓰여 있는 수가 0이면
    {
        map[ny][nx] = d[6];//주사위의 바닥면에 쓰여 있는 수 복사
    }
    else // 0이 아닌 경우
    {
        d[6] = map[ny][nx]; // 칸에 쓰여 있는 수를 주사위 바닥면으로 복사
        map[ny][nx] = 0; // 칸에 쓰여 있는 수 0으로
    }
 
    printf("%d\n", d[1]);
}
 
int main()
{
    //freopen("input.txt", "r", stdin);
    //setbuf(stdout, NULL);
 
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n >> m >> sy >> sx >> k;
 
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> map[i][j];
        }
    }
    int temp;
    for (int i = 0; i < k; i++)
    {
        cin >> temp;
        dmove(temp); // 주사위 이동
    }
 
    return 0;
}

 

'Algorithm > boj' 카테고리의 다른 글

백준 2110번 공유기 설치  (1) 2021.10.24
백준 14890번 경사로  (0) 2019.11.11
백준 14503 로봇 청소기  (0) 2019.11.11
백준 15662번 톱니바퀴 (2)  (0) 2019.11.10
백준 14891번 톱니바퀴  (0) 2019.11.10

+ Recent posts

티스토리툴바