https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRF8s6ezEDFAUo&categoryId=AWXRF8s6ezEDFAUo&categoryType=CODE



조건에 따라 공의 움직임을 구현해주면 된다.


출발 가능 지점에서 모든 방향으로 공을 출발시켜줬다.


웜홀의 위치는 STL map을 이용해서 기록했다.




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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
#include<iostream>
#include<map>
#include<vector>
using namespace std;
typedef pair<int, int> pii;
 
const int dr[4] = { 0,0,1,-1 };
const int dc[4] = { 1,-1,0,0 };
 
int m[101][101], n;
int cnt = 0, Max = 0;
map<pii, pii> mp;
 
bool forWorm[11];
//pii wormSave[11];
 
 
void process(int r, int c, int dir) {
    
    int nr = r, nc = c; //시작점 보존
 
    while (1) {
 
         nr += dr[dir]; //방향따라 이동
         nc += dc[dir];
 
        if (!(nr < 0 || nc < 0 || nr >= n || nc >= n)) // 종료 조건
            if (m[nr][nc] == -1 || (nr == r && nc == c)) 
                break;
            
        int num = m[nr][nc]; //다음 지점 정보
        
        if (nr < 0 || nc < 0 || nr >= n || nc >= n) {
            cnt++;
            if (dir == 0)  //동쪽으로
                dir = 1;
            else if (dir == 1) //서쪽
                dir = 0;
            else if (dir == 2) // 남쪽
                dir = 3;
            else //북쪽
                dir = 2;
        }
        else if (num >= 1 && num <= 5) {
            //블록만난경우
            cnt++; //점수추가
            if (num == 1) {
                if (dir == 0)  //동쪽으로
                    dir = 1;
                else if (dir == 1) //서쪽
                    dir = 3;
                else if (dir == 2) // 남쪽
                    dir = 0;
                else //북쪽
                    dir = 2;
            }
            else if (num == 2) {
                if (dir == 0)  //동쪽으로
                    dir = 1;
                else if (dir == 1) //서쪽
                    dir = 2;
                else if (dir == 2) // 남쪽
                    dir = 3;
                else //북쪽
                    dir = 0;
            }
            else if (num == 3) {
                if (dir == 0)  //동쪽으로
                    dir = 2;
                else if (dir == 1) //서쪽
                    dir = 0;
                else if (dir == 2) // 남쪽
                    dir = 3;
                else //북쪽
                    dir = 1;
            }
            else if (num == 4) {
                if (dir == 0)  //동쪽으로
                    dir = 3;
                else if (dir == 1) //서쪽
                    dir = 0;
                else if (dir == 2) // 남쪽
                    dir = 1;
                else //북쪽
                    dir = 2;
            }
            else {
                if (dir == 0)  //동쪽으로
                    dir = 1;
                else if (dir == 1) //서쪽
                    dir = 0;
                else if (dir == 2) // 남쪽
                    dir = 3;
                else //북쪽
                    dir = 2;
            }
        }
        else if (num >= 6 && num <= 10) {
            pii jumpTo = mp[{nr, nc}];
            nr = jumpTo.first;
            nc = jumpTo.second;
        }
    }
}
 
int main(void) {
    //setbuf(stdout, NULL);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int T;
    cin >> T;
    for (int t = 1; t <= T; t++) {
        vector<pii> wormSave(11);
        cin >> n;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cin >> m[i][j];
                if (m[i][j] >= 6 &&  m[i][j] <= 10) {
                    if (!forWorm[m[i][j]]) { //처음 나온 웜홀 번호
                        forWorm[m[i][j]] = true;
                        wormSave[m[i][j]] = { i, j };
                    }
                    else {
                        mp.insert({ { i, j }, { wormSave[m[i][j]] } });
                        mp.insert({ { wormSave[m[i][j]] } ,{ i, j } });
                    }
                }
            }
        }
 
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (m[i][j] != 0) continue; //빈공간에서만 시작
                for (int k = 0; k < 4; k++) {
                    //i, j 시작점 , 시작방향 k
                    process(i, j, k);
                    //printf("%d %d에서 %d방향으로 출발하면 결과 %d\n", i, j, k, cnt);
                    if (cnt > Max) {
                        Max = cnt;
                        
                    }
                    //초기화할거 초기화
                    cnt = 0;
                }
            }
        }
 
        //웜홀 리스트 확인
        /*for (map<pii, pii>::iterator itr = mp.begin(); itr != mp.end(); itr++) {
            printf("%d %d 넣으면 %d %d\n", itr->first.first, itr->first.second, itr->second.first, itr->second.second);
        }*/
 
        cout << "#" << t << ' ' << Max << '\n';
 
        //초기화
        mp.clear();
        wormSave.clear();
        for (int i = 6; i < 11; i++)
            forWorm[i] = false;
        Max = 0;
    }
 
    return 0;
}
 
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 삼성 SW Expert Academy' 카테고리의 다른 글

SWEA 2112: 보호 필름 (C++)  (0) 2019.10.17
SWEA 1767: 프로세서 연결하기 (C++)  (0) 2019.10.17
SWEA 5653:줄기세포배양 (C++)  (0) 2019.10.16
SWEA 2117: 홈 방범 서비스 (C++)  (0) 2019.10.16
SWEA 2382: 미생물 격리 (C++)  (0) 2019.10.16

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV597vbqAH0DFAVl



조건대로 시뮬레이션을 해주면 된다.


이동할 때, 이동한 개체와 앞으로 이동해야 하는 개체가 겹치는 처리를 하기 위해서 임시적으로 이차원 배열을 만들어서 이동할 때 사용했다.


이동 결과를 임시 배열에 저장해두고, 여러 개체가 들어있는 좌표를 처리해준 이후에, 원래의 map에 옮겨준다.



낚시왕, 나무재테크 문제와 비슷한 방식이 사용되었다.



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
#include<iostream>
#include<vector>
#include<algorithm>
 
using namespace std;
const int dr[4] = { -1,1,0,0 };
const int dc[4] = { 0,0,-1,1 };
 
struct Info {
    int num;
    int dir; //상하좌우 1234
};
 
vector<Info> map[101][101];
vector<Info> tmp[101][101]; //이동할 때 사용
int n, Time, k;
 
bool cmp(Info a, Info b) {
    return a.num > b.num;
}
int main(void) {
    //setbuf(stdout, NULL);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T;
    cin >> T;
 
    for (int t = 1; t <= T; t++) {
        cin >> n >> Time >> k;
        for (int i = 0; i < k; i++) {
            int r, c, cnt, dir;
            cin >> r >> c >> cnt >> dir;
            map[r][c].push_back({ cnt, dir });
        }
 
 
        for (int i = 0; i < Time; i++) {
            
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    //이동
                    if (map[i][j].size() != 0) {
                        Info cur = map[i][j][0];
 
                        int nr = i + dr[cur.dir - 1];
                        int nc = j + dc[cur.dir - 1];
 
                        if (nr == 0) {
                            cur.dir = 2;
                            cur.num /= 2;
                        }
                        else if (nr == n - 1) {
                            cur.dir = 1;
                            cur.num /= 2;
                        }
                        else if (nc == 0) {
                            cur.dir = 4;
                            cur.num /= 2;
                        }
                        else if (nc == n - 1) {
                            cur.dir = 3;
                            cur.num /= 2;
                        }
                        tmp[nr][nc].push_back({ cur.num, cur.dir });
 
                        map[i][j].clear(); //초기화
                    }
 
                }
            }
 
            //tmp에 들어있는 복수개 병합, 방향 설정
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (tmp[i][j].size() >= 2) {
                        sort(tmp[i][j].begin(), tmp[i][j].end(), cmp);
                        //개체수 내림차순
 
                        int Sum = 0;
                        for (int k = 0; k < tmp[i][j].size(); k++)
                            Sum += tmp[i][j][k].num;
 
                        Info merged = { Sum, tmp[i][j][0].dir }; //가장 많이 가진 것의 방향
                        map[i][j].push_back(merged);
                        tmp[i][j].clear(); //초기화
                    }
                    else if (tmp[i][j].size() == 1) {
                        map[i][j].push_back(tmp[i][j][0]);
                        tmp[i][j].clear(); //초기화
                    }
                }
            }
 
        }
 
        int ans = 0;
        for (int i = 0; i < n; i++) 
            for (int j = 0; j < n; j++) 
                if (map[i][j].size() != 0) {
                    ans += map[i][j][0].num;
                    map[i][j].clear(); //초기화
                }
            
        cout << "#" << t << ' ' << ans << '\n';
    }
 
    
    return 0;
}
 
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 삼성 SW Expert Academy' 카테고리의 다른 글

SWEA 5653:줄기세포배양 (C++)  (0) 2019.10.16
SWEA 2117: 홈 방범 서비스 (C++)  (0) 2019.10.16
SWEA 2383: 점심 식사시간 (C++)  (0) 2019.10.15
SWEA 4014: 활주로 건설 (C++)  (0) 2019.10.15
SWEA 2105: 디저트 카페 (C++)  (0) 2019.10.15

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRDL1aeugDFAUo&categoryId=AWXRDL1aeugDFAUo&categoryType=CODE




문제에서, 행과 열을 기존에 사용하던 방식과 다르게 사용하고 있기 때문에, 기존에 익숙한 방식으로 바꿔주었다.


남쪽으로 갈수록 행이 증가하고, 동쪽으로 가면 열이 증가하는 방식으로.



그리고 2차원 배열 안에 pair 벡터를 담았다.


벡터로 담은 이유는, 특정 지점에서 충전기 여러개의 영향을 받을 수 있기 때문이다.


그리고 벡터를 pair로 받은 이유는 충전세기와 함께 어떤 충전기의 영향을 받는지 확인할 수 있어야, 중복 충전때 충전 값 조절해주는 처리를 할 수 있기 때문이다.


이렇게 틀을 잡아두고, BFS를 이용해서 충전 영역을 map에 포시하였다.




다음으로, 간단한 경우부터 생각해보면


A와 B중 하나만 충전 영역에 위치하고 있다면, 그 위치에서 최대 충전량으로 충전을 하면 된다. 따라서 아까 pair 벡터를 충전량 내림차순으로 정렬해두고 사용한다.


나머지 경우는 A와 B 모두 1개 이상의 충전 영역을 지나고 있는 경우이다.


이 경우에는 모든 경우를 다 조사해서 최대 충전량을 찾아줘야 하기 때문에, 이중 for문을 통해서 최대 충전량을 찾아준다.



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
130
131
132
133
134
135
136
137
#include<vector>
#include<queue>
#include<iostream>
#include<algorithm>
using namespace std;
typedef pair<int, int> pii;
 
int pathA[101], pathB[101];
 
vector<pii> map[11][11];
 
const int dr[4] = { 0,0,1,-1 };
const int dc[4] = { 1,-1,0,0 };
struct BC {
    int r, c, range, pwr;
} bc[9];
 
queue<pii> q;
int dis[11][11];
void bfs(BC st, int num) {
    q.push({st.r, st.c});
 
    dis[st.r][st.c]++;
    map[st.r][st.c].push_back({ st.pwr, num});
 
    while (!q.empty()) {
        pii cur = q.front();
        q.pop();
        if (dis[cur.first][cur.second] >= st.range) continue;
        for (int i = 0; i < 4; i++) {
            int nr = cur.first + dr[i];
            int nc = cur.second + dc[i];
            if (dis[nr][nc] >= 0)continue;
            
            q.push({ nr, nc });
            dis[nr][nc] = dis[cur.first][cur.second] + 1;
            map[nr][nc].push_back({st.pwr, num});
        }
    }
}
 
bool cmp(pii a, pii b) { //충전량 내림차순 정렬
    return a.first > b.first;
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
 
    int T;
    cin >> T;
    for (int tc = 1; tc <= T; tc++) {
        int moves, cnt;
        cin >> moves >> cnt;
        for (int i = 0; i < moves; i++) 
            cin >> pathA[i];
        for (int i = 0; i < moves; i++)
            cin >> pathB[i];
        
        for (int i = 0; i < cnt; i++) {
            cin >> bc[i].c >> bc[i].r >> bc[i].range >> bc[i].pwr;
 
            for (int i = 1; i <= 10; i++)
                for (int j = 1; j <= 10; j++)
                    dis[i][j] = -1;
            bfs(bc[i], i); //배터리 충전 영역 그리기
        }
        
        //충전량 큰 것부터 나오도록 정렬
        for (int i = 1; i <= 10; i++)
            for (int j = 1; j <= 10; j++)
                if (map[i][j].size() > 1)
                    sort(map[i][j].begin(), map[i][j].end(), cmp);
 
        
        int Sum = 0, ar = 1, ac = 1, br = 10, bc = 10; //a의 row, a의 col ...
        for (int i = 0; i <= moves; i++) {
            
            int difA = 0 , difB = 0; //충전량 변수
            
            if (map[ar][ac].size() >= 1 && map[br][bc].size() >= 1) {
                //둘다 1개 이상 선택 가능
                int Max = -1;
                for (int k = 0; k < map[ar][ac].size(); k++) {
                    difA = map[ar][ac][k].first;
                    for (int p = 0; p < map[br][bc].size(); p++) {
                        difB = map[br][bc][p].first;
                        if (map[ar][ac][k].second == map[br][bc][p].second)
                            difB = 0; //a에서 사용한 걸 b에서도 사용하는 경우
                        if (difA + difB > Max) Max = difA + difB;
                    }
                }
                Sum += Max;
            }
            else if (map[ar][ac].size() == 0 && map[br][bc].size() > 0) 
                Sum += map[br][bc][0].first; //B만 충전 영역에 들어간 경우
 
            else if (map[ar][ac].size() > 0 && map[br][bc].size() == 0)
                Sum += map[ar][ac][0].first; //A만 충전 영역에 들어간 경우 
 
            //printf("%d초  A = %d B = %d\n", i, difA, difB);
 
            if (i == moves) break; //n초 이후로는 갱신되지 않도록
 
 
            //위치 이동
            if (pathA[i] == 1)
                ar--;
            else if (pathA[i] == 2)
                ac++;
            else if (pathA[i] == 3)
                ar++;
            else if (pathA[i] == 4)
                ac--;
 
            if (pathB[i] == 1)
                br--;
            else if (pathB[i] == 2)
                bc++;
            else if (pathB[i] == 3)
                br++;
            else if (pathB[i] == 4)
                bc--;
        }
 
        cout << "#" << tc << ' ' << Sum << '\n';
        //map초기화
        for (int i = 1; i <= 10; i++)
            for (int j = 1; j <= 10; j++)
                if (map[i][j].size() != 0)
                    map[i][j].clear();
    }
 
    return 0;
}
 
 
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 삼성 SW Expert Academy' 카테고리의 다른 글

SWEA 2115: 벌꿀채취 (C++)  (0) 2019.10.14
SWEA 1953: 탈주범 검거 (C++)  (0) 2019.10.13
SWEA 4008번: 숫자 만들기 (C++)  (0) 2019.10.08
SWEA 1952: 수영장 (C++)  (0) 2019.10.04
SWEA 4013번: 특이한 자석 (C++)  (0) 2019.10.03

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeV9sKkcoDFAVH&categoryId=AWIeV9sKkcoDFAVH&categoryType=CODE



백준에 있는 톱니바퀴 문제와 동일한 문제이다.



회전에 대한 구현은 다른 자석과 인접한 위치의 인덱스를 조절하는 것으로 처리할 것이다.


12시 방향의 인덱스를 0이라고 하면, 시계 방향으로 극들이 0~7의 인덱스를 가지고 주어진다.


초기에 왼쪽의 인덱스는 6, 오른쪽의 인덱스는 2, 12시 방향의 인덱스는 0이다.



가령 1번 톱니를 회전하면서 2번 톱니의 움직임을 확인한다고 하면, 1번의 right와 2번의 left를 비교해서 2번의 회전 여부를 결정해주는 방식이다.


만약 자석이 시계 방향으로 회전한다면, left, right 인덱스를 1씩 감소시켜준다. 반대의 경우에는 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
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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
 
#include<iostream>
using namespace std;
 
int mag[5][8];
int k;
int red[5], lft[5], rgt[5];
 
void changePos(int idx, int dir) { //회전하면서 생기는 인접한 지점, 12시 방향 변화
    if (dir == 1) {
        rgt[idx]--;
        red[idx]--;
        lft[idx]--;
        if (rgt[idx] < 0) rgt[idx] = 7;
        if (red[idx] < 0) red[idx] = 7;
        if (lft[idx] < 0) lft[idx] = 7;
    }
    else {
        rgt[idx]++;
        red[idx]++;
        lft[idx]++;
        if (rgt[idx] > 7) rgt[idx] = 0;
        if (red[idx] > 7) red[idx] = 0;
        if (lft[idx] > 7) lft[idx] = 0;
    }
}
 
void rotate(int num, int dir) {
    if (num == 1) {
        bool spin2 = false;
        if (mag[1][rgt[1]] != mag[2][lft[2]])
            spin2 = true;
 
        changePos(1, dir);//1번 회전
 
        if (spin2) { //1번때문에 2번도 돌아가는 경우
 
            //2번때문에 3번도 돌아야 하는지 확인
            bool spin3 = false;
            if (mag[2][rgt[2]] != mag[3][lft[3]]) spin3 = true;
            changePos(2, dir * -1); //2번 회전
 
            if (spin3) {
                //3번때문에 4번도 돌아야하는지 확인
                bool spin4 = false;
                if (mag[3][rgt[3]] != mag[4][lft[4]]) spin4 = true;
                changePos(3, dir); //3번 회전
 
                if (spin4) changePos(4, dir * -1); //4번 회전
            }
        }
    }
 
    else if (num == 2) {
        bool spin1 = false;
        if (mag[2][lft[2]] != mag[1][rgt[1]]) spin1 = true; //2번떄문에 1번 도는지 확인
 
        bool spin3 = false;
        if (mag[2][rgt[2]] != mag[3][lft[3]]) spin3 = true; //2번떄문에 3번 도는지 확인
 
        changePos(2, dir); //2번 회전
 
        if (spin1) changePos(1, dir * -1); //1번 회전
 
 
 
        if (spin3) {
            //3번때문에 4번도 돌아야하는지 확인
            bool spin4 = false;
            if (mag[3][rgt[3]] != mag[4][lft[4]]) spin4 = true;
            changePos(3, dir * -1); //3번 회전
 
            if (spin4) changePos(4, dir); //4번 회전
        }
 
    }
 
    else if (num == 3) {
        bool spin2 = false;
        if (mag[2][rgt[2]] != mag[3][lft[3]]) spin2 = true; //3번때문에 2번도는지
 
        bool spin4 = false;
        if (mag[3][rgt[3]] != mag[4][lft[4]]) spin4 = true; //3번때문에 4번도는지
 
        changePos(3, dir); //3번회전
 
        if (spin4) changePos(4, dir * -1); //4번회전
 
        if (spin2) {
            //2번때문에 1번도는지
            bool spin1 = false;
            if (mag[1][rgt[1]] != mag[2][lft[2]]) spin1 = true;
 
            changePos(2, dir * -1);
 
            if (spin1) changePos(1, dir);
        }
    }
 
    else if (num == 4) {
        //4번때문에 3번 도는지 확인
        bool spin3 = false;
        if (mag[4][lft[4]] != mag[3][rgt[3]]) spin3 = true;
 
        //4번 회전
        changePos(4, dir);
 
        if (spin3) {
            //3번때문에 2번도는지 확인
            bool spin2 = false;
            if (mag[2][rgt[2]] != mag[3][lft[3]]) spin2 = true;
 
            changePos(3, dir * -1);
 
            if (spin2) {
                //2번때문에 1번 도는지 확인
                bool spin1 = false;
                if (mag[1][rgt[1]] != mag[2][lft[2]]) spin1 = true;
 
                changePos(2, dir);
 
                if (spin1) changePos(1, dir * -1);
            }
        }
    }
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
 
    int T;
    cin >> T;
 
    for (int tc = 1; tc <= T; tc++) {
        for (int i = 1; i <= 4; i++) {
            lft[i] = 6;
            rgt[i] = 2;
            red[i] = 0;
        }
 
        cin >> k;
        for (int i = 1; i <= 4; i++)
            for (int j = 0; j < 8; j++)
                cin >> mag[i][j];
 
        while (k--) {
            int num, dir;
            cin >> num >> dir;
            rotate(num, dir);
 
        }
 
        int res = 0;
        if (mag[1][red[1]] == 1) res += 1;
        if (mag[2][red[2]] == 1) res += 2;
        if (mag[3][red[3]] == 1) res += 4;
        if (mag[4][red[4]] == 1) res += 8;
 
        cout << "#" << tc << ' ' << res << '\n';
 
 
    }
    return 0;
}
 
 
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 삼성 SW Expert Academy' 카테고리의 다른 글

SWEA 4008번: 숫자 만들기 (C++)  (0) 2019.10.08
SWEA 1952: 수영장 (C++)  (0) 2019.10.04
SWEA 4012번: 요리사 (C++)  (0) 2019.10.03
SWEA 1244번: 최대 상금 (C++)  (2) 2019.09.27
SWEA 3752번: 가능한 시험 점수 (C++)  (0) 2019.09.27

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


각각의 행과 열에대해서 인덱스가 증가하는 방향으로 한 번, 감소하는 방향으로 두 번 탐색을 진행하면서 예외 처리를 해주었다.


같은 높이가 몇개가 연속되는지 찾아서, 입력으로 주어지는 L과 비교하는 것이 관건인데, 1 1 2 2 이런식으로 증가하는 값에 대한 것은 그 개수를 파악하기 쉽지만, 2 2 1 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
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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
/*
cnt == n이면 경로 확정
루프시작 인덱스로 다시 돌아오면 가능 확정
차이가 2이상이면 경로 불가능 확정
cnt < len 인데 증가하면 불가능 확정
경사로 설치한 곳에 또 설치하려고 하면 불가능 확정
*/
#include<iostream>
using namespace std;
int n, len, m[102][102], Rchk[102], Cchk[102];
bool vis[102][102];
int main(void) {
    cin >> n >> len;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> m[i][j];
    
    for (int i = 0; i < n; i++) {
        int cnt = 1;
        for (int j = 1; j < n ; j++) { //col 증가
            if (m[i][j] == m[i][j - 1]) cnt++; //cnt == len이면 확정 -> chk = 1로
            else if (m[i][j] - m[i][j - 1] >= 2) {
                Rchk[i] = -1;
                break;
            }
            else if (m[i][j] > m[i][j - 1] && cnt < len) {
                Rchk[i] = -1;
                break;
            }
            else if (m[i][j] - m[i][j - 1] == 1 && cnt >= len) {
                for (int k = j - 1; k >= j - len; k--) {
                    vis[i][k] = true;
                }
                cnt = 1;
            }
            else if (m[i][j] < m[i][j - 1]) cnt = 1;
            
        }
        if (cnt == n) {
            Rchk[i] = 1;
            continue;
        }
        
        //col 감소
        if (Rchk[i] == -1 || Rchk[i] == 1) continue; //이미 위에서 확정 했으면 스킵
        cnt = 1;
        for (int j = n - 2; j >= 0; j--) {
            bool endFlag = false;
            if (m[i][j] == m[i][j + 1]) cnt++;
            else if (m[i][j] - m[i][j + 1] >= 2) {
                Rchk[i] = -1;
                break;
            }
            else if (m[i][j] > m[i][j + 1] && cnt < len) {
                Rchk[i] = -1;
                break;
            }
            else if (m[i][j] - m[i][j + 1] == 1 && cnt >= len) {
                for (int k = j + 1; k <= j + len; k++) {
                    if (vis[i][k]) {//설치한 곳에 또 설치하려고 하는 경우
                        Rchk[i] = -1;
                        endFlag = true;
                        break;
                    }
                    else
                        vis[i][k] = true;
                }
                if (endFlag) break;
                cnt = 1;
            }
            else if (m[i][j] < m[i][j + 1]) cnt = 1;
            if (j == 0) Rchk[i] = 1;
        }
    }
 
    
    //경사로 놨던거 초기화
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++)
            vis[i][j] = false;
    }
 
 
    for (int i = 0; i < n; i++) {
        int cnt = 1;
        for (int j = 1; j < n; j++) { //col 증가
            if (m[j][i] == m[j-1][i]) cnt++; //cnt == len이면 확정 -> chk = 1로
            else if (m[j][i] - m[j-1][i] >= 2) {
                Cchk[i] = -1;
                break;
            }
            else if (m[j][i] > m[j-1][i] && cnt < len) {
                Cchk[i] = -1;
                break;
            }
            else if (m[j][i] - m[j-1][i] == 1 && cnt >= len) {
                for (int k = j - 1; k >= j - len; k--) {
                    vis[k][i] = true;
                }
                cnt = 1;
            }
            else if (m[j][i] < m[j-1][i]) cnt = 1;
 
 
        }
        if (cnt == n) {
            Cchk[i] = 1;
            continue;
        }
 
        //col 감소
        if (Cchk[i] == -1 || Cchk[i] == 1) continue; //이미 위에서 확정 했으면 스킵
        cnt = 1;
        for (int j = n - 2; j >= 0; j--) {
            bool endFlag = false;
            if (m[j][i] == m[j+1][i]) cnt++;
            else if (m[j][i] - m[j+1][i] >= 2) {
                Cchk[i] = -1;
                break;
            }
            else if (m[j][i] > m[j+1][i] && cnt < len) {
                Cchk[i] = -1;
                break;
            }
            else if (m[j][i] - m[j+1][i] == 1 && cnt >= len) {
                for (int k = j + 1; k <= j + len; k++) {
                    if (vis[k][i]) {//설치한 곳에 또 설치하려고 하는 경우
                        Cchk[i] = -1;
                        endFlag = true;
                        break;
                    }
                    else
                        vis[k][i] = true;
                }
                if (endFlag) 
                    break;
                
                cnt = 1;
            }
            else if (m[j][i] < m[j+1][i]) cnt = 1;
            if (j == 0) Cchk[i] = 1;
        }
    }
    
    int res = 0;
    for (int i = 0; i < n; i++) {
        if (Rchk[i] == 1) res++;
        if (Cchk[i] == 1) res++;
    }
    cout << res;
 
    return 0;
}
 
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 17069번: 파이프 옮기기 2 (C++)  (0) 2019.08.09
백준 17070번: 파이프 옮기기 1 (C++)  (0) 2019.08.09
백준 14889번: 스타트와 링크 (C++)  (0) 2019.08.07
백준 14891번: 톱니바퀴 (C++)  (0) 2019.08.07
백준 15683번: 감시 (C++)  (0) 2019.08.07

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



문제를 보면, 톱니가 돌아가는 연산은 시계 방향으로 돌리거나 반시계 방향으로 돌리거나 둘 중 하나이다.


덮어 씌워지는 인덱스가 어떤 것인지 유의하면서 톱니의 회전을 구현해준 이후에는, 문제의 조건에 맞게 상황을 구현해주면 된다.


1번 톱니가 회전하면, 회전하기 이전의 상태에 따라서 2번 톱니가 회전을 할 수도 있고 그렇지 않을 수도 있다.


이렇게 각 번호마다 다르지만 비슷한 패턴으로 조건이 주어져 있기 때문에, 실수하지 않도록 하며 착실하게 구현해주면 되겠다.




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
#include<iostream>
 
using namespace std;
 
int ring[5][9]; //1~4, 0~7
void rotate(int idx, int dir) {
    if (dir == -1) {//반시계
        
        int tmp = ring[idx][7];
        for (int i = 0; i <= 6; i++) {
            int move = i - 1;
            if (move < 0) move = 7;
            ring[idx][move] = ring[idx][i];
        }
        ring[idx][6] = tmp;
    }
    else if (dir == 1) {    //시계
        int tmp = ring[idx][7];
        for (int i = 6; i >= 0; i--) {
            int move = i + 1;
            ring[idx][move] = ring[idx][i];
        }
        ring[idx][0] = tmp;
    }
}
void process(int idx, int dir) {
 
    if (idx ==1) { //1번 톱니
        bool re2 = false; //또 돌려야 하는지
        if (ring[idx][2] != ring[idx + 1][6]) re2 = true; //접점 극 다르면 또 돌리기
        
        rotate(idx, dir);
        
        //또돌리는 처리
        if (re2) {
            bool re3 = false;
            if (ring[2][2] != ring[3][6]) re3 = true;
            //3번이랑 접점 확인
            rotate(2, dir * -1);
            
            if (re3) {
                bool re4 = false;
                if (ring[3][2] != ring[4][6]) re4 = true;
                rotate(3, dir);
                
                if (re4) rotate(4, dir * -1);
            }
        }
    }
    
    else if (idx == 2) {
        bool re1 = false, re3 = false;
        if (ring[1][2] != ring[2][6]) re1 = true;
        if (ring[2][2] != ring[3][6]) re3 = true;
        rotate(2, dir);
        
        if (re1) rotate(1, dir * -1);
        
        if (re3) {
            bool re4 = false;
            if (ring[3][2] != ring[4][6]) re4 = true;
            rotate(3, dir * -1);
            
            if (re4) rotate(4, dir);
        }
    }
    
    else if (idx == 3) {
        bool re2 = false, re4 = false;
        if (ring[2][2] != ring[3][6]) re2 = true;
        if (ring[3][2] != ring[4][6]) re4 = true;
        rotate(3, dir);
        
        if (re2) {
            bool re1 = false;
            if (ring[2][6] != ring[1][2]) re1 = true;
            rotate(2, dir * -1);
            if (re1) rotate(1, dir);
        }
        if (re4) rotate(4, dir * -1);
    }
    else if (idx == 4) {
        bool re3 = false;
        if (ring[4][6] != ring[3][2]) re3 = true;
        rotate(4, dir);
        if (re3) {
            bool re2 = false;
            if (ring[3][6] != ring[2][2]) re2 = true;
            rotate(3, dir * -1);
            if (re2) {
                bool re1 = false;
                if (ring[2][6] != ring[1][2]) re1 = true;
                rotate(2, dir);
                if (re1) rotate(1, dir * -1);
            }
        }
    }
}
 
int main(void) {
    for (int i = 1; i <= 4; i++)
        for (int j = 0; j < 8; j++)
            scanf("%1d", &ring[i][j]);
 
    int num;
    cin >> num;
    while (num--) {
        int idx, dir;
        cin >> idx >> dir;
        process(idx, dir);
    }
    int score = 0;
    for (int i = 1; i <= 4; i++) {
        if (ring[i][0] == 1 && i == 1) score++;
        else if (ring[i][0] == 1 && i == 2) score+= 2;
        else if (ring[i][0] == 1 && i == 3) score+= 4;
        else if (ring[i][0] == 1 && i == 4) score+= 8;
    }
    cout << score;
    return 0;
}
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 14890번: 경사로 (C++)  (0) 2019.08.09
백준 14889번: 스타트와 링크 (C++)  (0) 2019.08.07
백준 15683번: 감시 (C++)  (0) 2019.08.07
백준 14502번: 연구소 (C++)  (0) 2019.08.07
백준 15685번: 드래곤 커브 (C++)  (0) 2019.08.06

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



문제를 보면, 카메라의 전체 개수가 8개로 많지 않다. 카메라의 종류별로 가능한 각도들을 모두 시뮬레이션해주면 되겠다.


각각의 카메라가 가질 수 있는 상태를 번호로 지정했다. 1번 카메라는 0~3번 상태, 2번 카메라는 4번~5번 상태... 이런 방식이다.


이제 카메라들이 띄고 있을 수 있는 상태를 조합으로 뽑아주면 된다.



이때 1번 카메라는 0~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
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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
#include<iostream>
#include<vector>
 
using namespace std;
 
int R, C, map[10][10], tmp[10][10];
struct CAMPOS {
    int idx; //카메라 번호
    int r;
    int c;
};
vector<CAMPOS> cv;
bool isused[10][4]; //카메라 8개, 각도 사용 정보
bool masterUsage[9];
int cam[10][4]; //i번째 순서 카메라가 가질 수 있는 각도 저장
int arr[10], st = 0, st2 = 0, res = 100;
void init() {
    for (int i = 0; i < 10; i++)
        for (int j = 0; j < 4; j++)
            cam[i][j] = -1;
}
 
void process() {
    //arr에 카메라 각도 번호
    for (int i = 0; i < cv.size(); i++) {
        int cr = cv[i].r;
        int cc = cv[i].c;
        if (arr[i] == 0) {
            for (int j = cv[i].c + 1; j <= C - 1; j++) {//동
                if (map[cv[i].r][j] != 0 && map[cv[i].r][j] != 6) continue; //빈공간X and 벽X -> 카메라면 스킵
                if (map[cv[i].r][j] == 6) break;
                if (map[cv[i].r][j] == 0) map[cv[i].r][j] = 7; //감시 가능 영역을 7
            }
        }
        else if (arr[i] == 1) {
            for (int j = cv[i].r + 1; j <= R - 1; j++) {//남
                if (map[j][cv[i].c] != 0 && map[j][cv[i].c] != 6) continue; //빈공간X and 벽X -> 카메라면 스킵
                if (map[j][cv[i].c] == 6) break;
                if (map[j][cv[i].c] == 0) map[j][cv[i].c] = 7; //감시 가능 영역을 7
            }
        }
        else if (arr[i] == 2) {
            for (int j = cc - 1; j >= 0; j--) {//서
                if (map[cr][j] != 0 && map[cr][j] != 6) continue;
                if (map[cr][j] == 6) break;
                if (map[cr][j] == 0) map[cr][j] = 7;
            }
        }
        else if (arr[i] == 3) {
            for (int j = cr - 1; j >= 0; j--) {//북
                if (map[j][cc] != 0 && map[j][cc] != 6) continue;
                if (map[j][cc] == 6) break;
                if (map[j][cc] == 0) map[j][cc] = 7;
            }
        }
        else if (arr[i] == 4) {
            for (int j = cv[i].c + 1; j <= C - 1; j++) {//동
                if (map[cv[i].r][j] != 0 && map[cv[i].r][j] != 6) continue; //빈공간X and 벽X -> 카메라면 스킵
                if (map[cv[i].r][j] == 6) break;
                if (map[cv[i].r][j] == 0) map[cv[i].r][j] = 7; //감시 가능 영역을 7
            }
            for (int j = cc - 1; j >= 0; j--) {//서
                if (map[cr][j] != 0 && map[cr][j] != 6) continue;
                if (map[cr][j] == 6) break;
                if (map[cr][j] == 0) map[cr][j] = 7;
            }
        }
        else if (arr[i] == 5) {
            for (int j = cv[i].r + 1; j <= R - 1; j++) {//남
                if (map[j][cv[i].c] != 0 && map[j][cv[i].c] != 6) continue; //빈공간X and 벽X -> 카메라면 스킵
                if (map[j][cv[i].c] == 6) break;
                if (map[j][cv[i].c] == 0) map[j][cv[i].c] = 7; //감시 가능 영역을 7
            }
            for (int j = cr - 1; j >= 0; j--) {//북
                if (map[j][cc] != 0 && map[j][cc] != 6) continue;
                if (map[j][cc] == 6) break;
                if (map[j][cc] == 0) map[j][cc] = 7;
            }
        }
        else if (arr[i] == 6) {
            for (int j = cr - 1; j >= 0; j--) {//북
                if (map[j][cc] != 0 && map[j][cc] != 6) continue;
                if (map[j][cc] == 6) break;
                if (map[j][cc] == 0) map[j][cc] = 7;
            }
            for (int j = cv[i].c + 1; j <= C - 1; j++) {//동
                if (map[cv[i].r][j] != 0 && map[cv[i].r][j] != 6) continue; //빈공간X and 벽X -> 카메라면 스킵
                if (map[cv[i].r][j] == 6) break;
                if (map[cv[i].r][j] == 0) map[cv[i].r][j] = 7; //감시 가능 영역을 7
            }
        }
        else if (arr[i] == 7) {
            for (int j = cv[i].c + 1; j <= C - 1; j++) {//동
                if (map[cv[i].r][j] != 0 && map[cv[i].r][j] != 6) continue; //빈공간X and 벽X -> 카메라면 스킵
                if (map[cv[i].r][j] == 6) break;
                if (map[cv[i].r][j] == 0) map[cv[i].r][j] = 7; //감시 가능 영역을 7
            }
            for (int j = cv[i].r + 1; j <= R - 1; j++) {//남
                if (map[j][cv[i].c] != 0 && map[j][cv[i].c] != 6) continue; //빈공간X and 벽X -> 카메라면 스킵
                if (map[j][cv[i].c] == 6) break;
                if (map[j][cv[i].c] == 0) map[j][cv[i].c] = 7; //감시 가능 영역을 7
            }
        }
        else if (arr[i] == 8) {
            for (int j = cv[i].r + 1; j <= R - 1; j++) {//남
                if (map[j][cv[i].c] != 0 && map[j][cv[i].c] != 6) continue; //빈공간X and 벽X -> 카메라면 스킵
                if (map[j][cv[i].c] == 6) break;
                if (map[j][cv[i].c] == 0) map[j][cv[i].c] = 7; //감시 가능 영역을 7
            }
            for (int j = cc - 1; j >= 0; j--) {//서
                if (map[cr][j] != 0 && map[cr][j] != 6) continue;
                if (map[cr][j] == 6) break;
                if (map[cr][j] == 0) map[cr][j] = 7;
            }
        }
        else if (arr[i] == 9) {
            for (int j = cc - 1; j >= 0; j--) {//서
                if (map[cr][j] != 0 && map[cr][j] != 6) continue;
                if (map[cr][j] == 6) break;
                if (map[cr][j] == 0) map[cr][j] = 7;
            }
            for (int j = cr - 1; j >= 0; j--) {//북
                if (map[j][cc] != 0 && map[j][cc] != 6) continue;
                if (map[j][cc] == 6) break;
                if (map[j][cc] == 0) map[j][cc] = 7;
            }
        }
        else if (arr[i] == 10) {
            for (int j = cr - 1; j >= 0; j--) {//북
                if (map[j][cc] != 0 && map[j][cc] != 6) continue;
                if (map[j][cc] == 6) break;
                if (map[j][cc] == 0) map[j][cc] = 7;
            }
            for (int j = cv[i].c + 1; j <= C - 1; j++) {//동
                if (map[cv[i].r][j] != 0 && map[cv[i].r][j] != 6) continue; //빈공간X and 벽X -> 카메라면 스킵
                if (map[cv[i].r][j] == 6) break;
                if (map[cv[i].r][j] == 0) map[cv[i].r][j] = 7; //감시 가능 영역을 7
            }
            for (int j = cc - 1; j >= 0; j--) {//서
                if (map[cr][j] != 0 && map[cr][j] != 6) continue;
                if (map[cr][j] == 6) break;
                if (map[cr][j] == 0) map[cr][j] = 7;
            }
        }
        else if (arr[i] == 11) {
            for (int j = cr - 1; j >= 0; j--) {//북
                if (map[j][cc] != 0 && map[j][cc] != 6) continue;
                if (map[j][cc] == 6) break;
                if (map[j][cc] == 0) map[j][cc] = 7;
            }
            for (int j = cv[i].c + 1; j <= C - 1; j++) {//동
                if (map[cv[i].r][j] != 0 && map[cv[i].r][j] != 6) continue; //빈공간X and 벽X -> 카메라면 스킵
                if (map[cv[i].r][j] == 6) break;
                if (map[cv[i].r][j] == 0) map[cv[i].r][j] = 7; //감시 가능 영역을 7
            }
            for (int j = cv[i].r + 1; j <= R - 1; j++) {//남
                if (map[j][cv[i].c] != 0 && map[j][cv[i].c] != 6) continue; //빈공간X and 벽X -> 카메라면 스킵
                if (map[j][cv[i].c] == 6) break;
                if (map[j][cv[i].c] == 0) map[j][cv[i].c] = 7; //감시 가능 영역을 7
            }
        }
        else if (arr[i] == 12) {
            for (int j = cv[i].c + 1; j <= C - 1; j++) {//동
                if (map[cv[i].r][j] != 0 && map[cv[i].r][j] != 6) continue; //빈공간X and 벽X -> 카메라면 스킵
                if (map[cv[i].r][j] == 6) break;
                if (map[cv[i].r][j] == 0) map[cv[i].r][j] = 7; //감시 가능 영역을 7
            }
            for (int j = cv[i].r + 1; j <= R - 1; j++) {//남
                if (map[j][cv[i].c] != 0 && map[j][cv[i].c] != 6) continue; //빈공간X and 벽X -> 카메라면 스킵
                if (map[j][cv[i].c] == 6) break;
                if (map[j][cv[i].c] == 0) map[j][cv[i].c] = 7; //감시 가능 영역을 7
            }
            for (int j = cc - 1; j >= 0; j--) {//서
                if (map[cr][j] != 0 && map[cr][j] != 6) continue;
                if (map[cr][j] == 6) break;
                if (map[cr][j] == 0) map[cr][j] = 7;
            }
        }
        else if (arr[i] == 13) {
            for (int j = cv[i].r + 1; j <= R - 1; j++) {//남
                if (map[j][cv[i].c] != 0 && map[j][cv[i].c] != 6) continue; //빈공간X and 벽X -> 카메라면 스킵
                if (map[j][cv[i].c] == 6) break;
                if (map[j][cv[i].c] == 0) map[j][cv[i].c] = 7; //감시 가능 영역을 7
            }
            for (int j = cc - 1; j >= 0; j--) {//서
                if (map[cr][j] != 0 && map[cr][j] != 6) continue;
                if (map[cr][j] == 6) break;
                if (map[cr][j] == 0) map[cr][j] = 7;
            }
            for (int j = cr - 1; j >= 0; j--) {//북
                if (map[j][cc] != 0 && map[j][cc] != 6) continue;
                if (map[j][cc] == 6) break;
                if (map[j][cc] == 0) map[j][cc] = 7;
            }
        }
        else if (arr[i] == 14) {
            for (int j = cv[i].r + 1; j <= R - 1; j++) {//남
                if (map[j][cv[i].c] != 0 && map[j][cv[i].c] != 6) continue; //빈공간X and 벽X -> 카메라면 스킵
                if (map[j][cv[i].c] == 6) break;
                if (map[j][cv[i].c] == 0) map[j][cv[i].c] = 7; //감시 가능 영역을 7
            }
            for (int j = cc - 1; j >= 0; j--) {//서
                if (map[cr][j] != 0 && map[cr][j] != 6) continue;
                if (map[cr][j] == 6) break;
                if (map[cr][j] == 0) map[cr][j] = 7;
            }
            for (int j = cr - 1; j >= 0; j--) {//북
                if (map[j][cc] != 0 && map[j][cc] != 6) continue;
                if (map[j][cc] == 6) break;
                if (map[j][cc] == 0) map[j][cc] = 7;
            }
            for (int j = cv[i].c + 1; j <= C - 1; j++) {//동
                if (map[cv[i].r][j] != 0 && map[cv[i].r][j] != 6) continue; //빈공간X and 벽X -> 카메라면 스킵
                if (map[cv[i].r][j] == 6) break;
                if (map[cv[i].r][j] == 0) map[cv[i].r][j] = 7; //감시 가능 영역을 7
            }
        }
    }
}
void backTracking(int k) {
    if (k == cv.size()) {
 
        process();
 
        //사각지대 계산
        int cnt = 0;
        for (int i = 0; i < R; i++)
            for (int j = 0; j < C; j++)
                if (map[i][j] == 0) cnt++;
 
        if (res > cnt) 
            res = cnt;
 
        //원상복구
        for (int i = 0; i < R; i++)
            for (int j = 0; j < C; j++)
                map[i][j] = tmp[i][j];
        return;
    }
 
    if (k == 0) st = 0;
 
    for (int i = st; i < cv.size(); i++) {
        if (!masterUsage[i]) {
            masterUsage[i] = true;
            //i번카메라가 사용중이 아니면서
            //if (k == 0) st2 = 0;
            for (int j = 0; j < 4; j++) {
                if (cam[i][j] != -1 && !isused[i][j]) {
                    //존재하는 카메라 각도이면서 사용중이 아닌 각도라면
                    arr[k] = cam[i][j];
                    isused[i][j] = true;
                    st = i;
                    //st2 = j;
                    backTracking(k + 1);
                    isused[i][j] = false;
                }
            }
            masterUsage[i] = false;
        }
 
    }
 
}
int main(void) {
    ios::sync_with_stdio(false);
 
    cin >> R >> C;
    for (int i = 0; i < R; i++)
        for (int j = 0; j < C; j++) {
            cin >> map[i][j];
            tmp[i][j] = map[i][j];
            if (map[i][j] != 0 && map[i][j] != 6) {
                CAMPOS tmp;
                tmp.r = i;
                tmp.c = j;
                tmp.idx = map[i][j];
                cv.push_back(tmp); //cv에 카메라 정보 저장
            }
        }
 
    init();
 
    for (int i = 0; i < cv.size(); i++) {
        if (cv[i].idx == 1) {
            for (int j = 0; j < 4; j++)
                cam[i][j] = j;
        }
        else if (cv[i].idx == 2) {
            for (int j = 0; j < 2; j++)
                cam[i][j] = j + 4;
        }
        else if (cv[i].idx == 3) {
            for (int j = 0; j < 4; j++)
                cam[i][j] = j + 6;
        }
        else if (cv[i].idx == 4) {
            for (int j = 0; j < 4; j++)
                cam[i][j] = j + 10;
        }
        else if (cv[i].idx == 5) {
            cam[i][0] = 14;
        }
    }
 
    backTracking(0);
    cout << res << '\n';
 
}
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 14889번: 스타트와 링크 (C++)  (0) 2019.08.07
백준 14891번: 톱니바퀴 (C++)  (0) 2019.08.07
백준 14502번: 연구소 (C++)  (0) 2019.08.07
백준 15685번: 드래곤 커브 (C++)  (0) 2019.08.06
백준 15686번: 치킨 배달 (C++)  (0) 2019.08.05

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



특별한 알고리즘이랄 것이 필요하지 않은 전형적인 시뮬레이션 문제였다.


하지만 설계를 제대로 하고 들어가지 않으면 꽤 해맬 수 있었던 문제이다.



여느 시뮬레이션 문제들이 그러하듯이, 상황을 어떻게 표현할 것인가 생각해야 한다.


나는 주의 깊게 그림을 살펴보지 않아서 간과했던 사실이지만, 문제 설명에서 그림을 보여주면서 좌표 값을 그림 아래에 표시해줬다.



그것을 보면, 커브의 상태를 좌표에 찍을 수 있고, 좌표에 어떻게 찍히느냐는 기본적으로 세대가 결정하고,


같은 세대라고 할지라도 시작한 방향값이 다르다면 다르게 찍힌다는 것을 알 수 있다.



(0,0)에서 시작한 0세대 커브는 (1,0)으로 x값이 1증가한다.


그리고 이어서 2세대로 변천할 때, 1세대의 마지막 점(1,0)에서 (1,-1)로 이동하여 y좌표가 1감소하는 것을 알 수 있다.


이 상황은 0,0에서 시작한 d값이 1인 0세대의 커브이다.


만약 나머지 조건이 동일하고, 방향 값인 d값이 1이었다면?  0,0에서 시작한 커브는 상단으로 뻗었을 것이고


0세대 커브는 0,0에서 0,-1로 변천했을 것이다. 이런식으로 파악해나가야 한다.



방향이 0인 세대별 커브의 성분을 방향 숫자로 나타내보면,


0세대: 0


1세대: 0, 1


2세대: 0, 1, 2, 1


3세대: 0, 1, 2, 1, 2, 3, 2, 1


4세대: 0, 1, 2, 1, 2, 3, 2, 1, 2, 3, 0, 3, 2, 3, 2, 1


...


이런식으로 증가한다. 여기서 규칙을 확인할 수 있다. 먼저 개수가 2의 거듭제곱 꼴로 늘어나고 있다.


그리고 문제에서 주어진 조건과 연결해서 확인해보면, 이전 세대의 커브를 90도 돌리고 끝을 붙인다고 했다.


90도 돌린다는 것은 방향값의 변화를 의미하는 것이고, 끝을 붙인다는 것은, 성분을 뒤에서부터 하나씩 붙인다는 것이다.


따라서 0세대에서 1세대로 갈 때, 0에 1을 더한 1이 붙은 것이고, 1세대에서 2세대로 갈 때, 1세대의 마지막인 1에 1을 더한 값인 2가 붙고, 0에 1을 더한 값인 1이 그 뒤에 붙은 것이다.


이를 그냥 배열 인덱스로 조절해서 구해도 되겠지만 동작 구조가 스택과 같으니, 스택을 활용했다.



나는 방향 0의 드래곤커브의 10세대를 구해서 배열에 저장했다. 10세대를 구하면 곧, 앞부분에 0~9세대도 포함되어 있는 것이기 때문에 변형해서 사용하면 된다. 또한 방향 0의 값을 구해 놓았으니, 방향이 변하면 모든 성분을 더해줘서 방향을 바뀐 것처럼 사용하면 되고, %4를 통해 값이 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
#include<iostream>
#include<stack>
#include<vector>
using namespace std;
stack<int> stk;
int map[101][101];
int d[1025]; //0~3방향, 0~10세대
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
 
    for (int i = 1; i <= 10; i++) {
        for (int j = 0; j <= (1 << (i - 1)) - 1; j++) {
            stk.push(d[j]); //이전 세대의 것을 스택에 넣고
        }
        for (int j = 1 << (i - 1); j <= (1 << i) - 1; j++) {
            d[j] = (stk.top() + 1) % 4;
            stk.pop();
            //1씩 증가하면서 pop하면서 이전 세대의 것에 붙이면 현재 세대의 것이 나옴
        }
    }
 
    for (int i = 0; i < n; i++) {
        int x, y, dir, gen;
        cin >> x >> y >> dir >> gen;
        map[y][x] = 1;
        for (int j = 0; j <= (1 << gen) - 1; j++) {
            if ((d[j] + dir) % 4 == 0) {
                x++; //갱신하면서 움직여야 반영됨
                map[y][x] = 1;
            }
            else if ((d[j] + dir) % 4 == 1) {
                y--;
                map[y][x] = 1;
            }
            else if ((d[j] + dir) % 4 == 2) {
                x--;
                map[y][x] = 1;
            }
            else if ((d[j] + dir) % 4 == 3) {
                y++;
                map[y][x] = 1;
            }
        }
    }
    
    int cnt = 0;
    for (int i = 0; i < 100; i++) { //생각 없이 n까지만 잡으면 안 되고, x, y 최대 범위만큼
        for (int j = 0; j < 100; j++) { 
            if (map[i][j] == 1 && map[i][j + 1] == 1 &&
                map[i + 1][j] == 1 && map[i + 1][j + 1] == 1) cnt++;
        }
    }
    cout << cnt;
    return 0;
}
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 15683번: 감시 (C++)  (0) 2019.08.07
백준 14502번: 연구소 (C++)  (0) 2019.08.07
백준 15686번: 치킨 배달 (C++)  (0) 2019.08.05
백준 17141번: 연구소 2 (C++)  (0) 2019.08.05
백준 11050번: 이항 계수1 (C++)  (0) 2019.08.05

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

 

17143번: 낚시왕

낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. 칸에는 상어가 최대 한 마리 들어있을 수 있다. 상어는 크기와 속도를 가지고 있다. 낚시왕은 처음에 1번 열의 한 칸 왼쪽에 있다. 다음은 1초 동안 일어나는 일이며, 아래 적힌 순서대로 일어난다. 낚시왕은 가장 오른쪽 열의 오른쪽 칸에 이동하

www.acmicpc.net

필요한 상어에 대한 정보를 담아서 구조체를 만든다.

 

이후에는 착실하게 시뮬레이션을 진행해주면 된다.

 

 

 

 

나 같은 경우에는 이전에 나무재테크 문제를 풀 때를 떠올려서, 한 칸에 상어가 여러 마리 들어가는 경우가 생기기 때문에 배열로 벡터를 잡았다.

 

먼저 상어의 이동과 관련된 구현이다.

 

문제에서 상어의 속력은 1000까지 가능하다고 했는데, 이 부분에서 나름 연산의 횟수를 줄여보겠다고 행과 열의 길이를 활용해서 모듈러 연산을 사용했다.

 

그런데 생각하지 못한 부분이 있었어서 프린트를 찍어가며 디버깅을 하는 데에 애를 먹었다.

 

그냥 속편하게 속도만큼 반복문을 돌리면서 (완벽한 통제를 위해서 for문을 사용하는 것이 낫겠다) 속도만큼 칸을 이동해주고, 이동한 칸이 범위를 벗어난다면 다시 바로잡아주는 식으로 하는 것이 조금 더 쉽고 직관적으로 구현할 수 있는 방법인 것 같다.

 

다른 부분은 상어가 먹히는 부분이다.

 

나는 일단 상어는 다 칸에 들어갈 수 있고, 그 이후에 가장 큰 상어를 찾아서 그 상어만 두고 나머지 상어는 다 제거하는 방식으로 구현을 했다.

 

 

저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 11050번: 이항 계수1 (C++)  (0) 2019.08.05
백준 17142번: 연구소 3 (C++)  (0) 2019.08.05
백준 16235번: 나무 재테크 (C++)  (0) 2019.07.30
백준 16234번: 인구 이동 (C++)  (0) 2019.07.26
백준 17281번: 야구 ⚾ (C++)  (0) 2019.07.26

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

 

16235번: 나무 재테크

부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 떨어진 칸의 개수, c는 가장 왼쪽으로부터 떨어진 칸의 개수이다. r과 c는 1부터 시작한다. 상도는 전자통신공학과 출신답게 땅의 양분을 조사하는 로봇 S2D2를 만들었다. S2D2는 1×1 크기의 칸에 들어있는 양분을 조사해 상도에게 전송하고, 모든

www.acmicpc.net

 

특별한 알고리즘이랄 것이 없지만, 벡터를 활용하는 약간의 센스가 필요하다.

 

정수를 담는 벡터 자료형을 이차원 배열로 선언한다.

 

그래야 이차원 좌표상의 한 공간에 나무가 여러개 쌓이는 효과를 볼 수 있다.

 

그리고, 여름에 나무의 삭제가 발생할 때, 삭제되는 나무에 대한 처리를 할 때, vector.erase를 사용하고, 삭제되는 나무들에 대한 정보를 큐로 옮긴 이후에, 큐에서 pop하면서 처리를 해서 시간초과를 받았다.

 

이를 해결하기위해서, 봄에 땅으로부터 영양분을 흡수하는 것은 어짜피 나무가 나이로 정렬된 상태로 이루어지고, 특정 나이가 땅의 양분보다 많은 순간이 온다면, 그 나무보다 나이가 많은 나무들은 자연스럽게 확인할 가치가 없어지기 때문에, 봄에 영양분을 흡수했던 나무들을 임시 벡터에 넣어두고, 실패지점 이후에 원본 벡터를 clear한 이후에, 임시 벡터에 들어있는 데이터를 원래 벡터에 옮겨주면 여름에 대한 구현을 할 수 있다.

 

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
ll grd[11][11];
int igr[11][11], n, m, k;
vector<ll> v[11][11];
int dr[8] = { -1, -1, 0, 1, 1, 1, 0, -1 };
int dc[8] = { 0, 1, 1, 1, 0, -1, -1, -1 };
int main(void) {
	//1-indexed
	cin >> n >> m >> k;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> igr[i][j];
			grd[i][j] = 5;
		}
	}
	for (int i = 1; i <= m; i++) {
		int r, c, age;
		cin >> r >> c >> age;
		v[r][c].push_back(age);
	}
	for (int i = 1; i <= k; i++) {
		//봄
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (v[i][j].size() > 0) { //i행 j열에 나무가 존재하면
					vector<ll> tmp;
					sort(v[i][j].begin(), v[i][j].end()); //어린 나무부터
					//땅양분이 나이보다 많으면 나이 증가, 땅 양분 감소
					ll dead = 0;
					for (int t = 0; t < v[i][j].size(); t++) {
						if (v[i][j][t] <= grd[i][j]) {
							tmp.push_back(v[i][j][t] + 1);
							grd[i][j] -= v[i][j][t];
						}
						else {
							dead += v[i][j][t] / 2;
						}
					}
					//여름
					v[i][j].clear();
					v[i][j] = tmp;
					grd[i][j] += dead;
				}
			}
		}

		//가을
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (v[i][j].size() > 0) {
					for (int t = 0; t < v[i][j].size(); t++) {
						if (v[i][j][t] % 5 == 0) {
							for (int ii = 0; ii < 8; ii++) {
								int nr = i + dr[ii];
								int nc = j + dc[ii];
								if (nr < 1 || nc < 1 || nr > n || nc > n) continue;
								v[nr][nc].push_back(1);
							}
						}
					}
				}
			}
		}

		//겨울
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				grd[i][j] += igr[i][j];
			}
		}
	}
	ll cnt = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (v[i][j].size() > 0) cnt += v[i][j].size();
		}
	}
	cout << cnt;
	return 0;
}
저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 17142번: 연구소 3 (C++)  (0) 2019.08.05
백준 17143번: 낚시왕 (C++)  (0) 2019.08.04
백준 16234번: 인구 이동 (C++)  (0) 2019.07.26
백준 17281번: 야구 ⚾ (C++)  (0) 2019.07.26
백준 17144번: 미세먼지 안녕 (C++)  (0) 2019.07.25

+ Recent posts

티스토리툴바