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=AWIeW7FakkUDFAVH&categoryId=AWIeW7FakkUDFAVH&categoryType=CODE




백준에 있는 경사로 문제와 동일하다.


행을 확인할 때는 우측으로 증가하는 경우와, 감소하는 경우를 찾고 불가능한 경우는 걸러낸다.


열을 확인할 때는 하단으로 증가, 감소 경우에 대해서 동일하게 검색한다.



이미 경사로를 건설한 곳에 또 경사로를 건설하지 않도록 해야한다.



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
#include<iostream>
#include<cmath>
using namespace std;
 
int n, len, map[21][21];
bool used[21][21];
 
bool rowCheck(int i) {
 
    for (int j = 0; j < n-1; j++) {
        if (used[i][j + 1]) continue; //다음 지점에 이미 경사로 있으면
        if (abs(map[i][j] - map[i][j + 1]) >= 2) return false; //2이상 차이
        
        if (map[i][j] == map[i][j + 1] + 1) {
            if (j + len >= n) return false; //경사로 지으면 밖으로 나가는 경우
 
            for (int k = j + 1; k <= j + 1 + len - 2; k++) {
                if (map[i][k] != map[i][k + 1]) return false;
            }
 
            for (int k = j + 1; k <= j + 1 + len - 1; k++) { //이미 경사로가 놓인 경우
                if (used[i][k]) return false;
            }
            
            for (int k = j + 1; k <= j + len; k++) //경사로 표시
                used[i][k] = true;
        }
 
    }
 
    for (int j = 0; j < n-1; j++) {
        if (used[i][j + 1]) continue; //다음 지점에 이미 경사로 있으면
        
        if (map[i][j] == map[i][j + 1] - 1) {
            if (j + 1 - len < 0) return false; //경사로 지으면 밖으로 나가는 경우
 
            for (int k = j + 1 - len; k <= j - 1 ; k++) {
                if (map[i][k] != map[i][k + 1]) return false;
            }
 
            for (int k = j + 1 - len; k <= j; k++) { //이미 경사로가 놓인 경우
                if (used[i][k]) return false;
            }
 
            for (int k = j + 1 - len; k <= j ; k++) //경사로 표시
                used[i][k] = true;
        }
    }
    return true;
}
 
bool colCheck(int j) {
    for (int i = 0; i < n - 1; i++) {
        if (used[i+1][j]) continue; //다음 지점에 이미 경사로 있으면
        if (abs(map[i][j] - map[i+1][j]) >= 2) return false; //2이상 차이
 
        if (map[i][j] == map[i+1][j] + 1) {
            if (i + len >= n) return false; //경사로 지으면 밖으로 나가는 경우
 
            for (int k = i + 1; k <= i + 1 + len - 2; k++) {
                if (map[k][j] != map[k+1][j]) return false;
            }
 
            for (int k = i + 1; k <= i + 1 + len - 1; k++) {
                if (used[k][j]) return false;
            }
 
            for (int k = i + 1; k <= i + len; k++) //경사로 표시
                used[k][j] = true;
        }
 
    }
 
    for (int i = 0; i < n - 1; i++) {
        if (used[i+1][j]) continue; //다음 지점에 이미 경사로 있으면
 
        if (map[i][j] == map[i+1][j] - 1) {
            if (i + 1 - len < 0) return false; //경사로 지으면 밖으로 나가는 경우
 
            for (int k = i + 1 - len; k <= i - 1; k++) {
                if (map[k][j] != map[k+1][j]) return false;
            }
 
            for (int k = i + 1 - len; k <= i; k++) {
                if (used[k][j]) return false;
            }
 
            for (int k = i + 1 - len; k <= i; k++) //경사로 표시
                used[k][j] = true;
        }
    }
 
    return true;
}
 
int process() {
    int ret = 0; //활주로로 사용가능한 길
 
    for (int i = 0; i < n; i++) {
        if (!rowCheck(i)) //가로방향 확인
            continue;
        ret++;
    }
 
    //경사로 초기화
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            used[i][j] = false;
 
 
    for (int j = 0; j < n; j++) {
        if (!colCheck(j)) 
            continue;
        ret++;
    }
    
    return ret;
}
 
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 >> len;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                cin >> map[i][j];
 
        int res = process();
 
        cout << "#" << t << ' ' << res << '\n';
 
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                map[i][j] = 0;
 
        //경사로 초기화
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                used[i][j] = false;
 
    }
 
    return 0;
}
 
cs


저작자표시 비영리 변경금지 (새창열림)

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

SWEA 2382: 미생물 격리 (C++)  (0) 2019.10.16
SWEA 2383: 점심 식사시간 (C++)  (0) 2019.10.15
SWEA 2105: 디저트 카페 (C++)  (0) 2019.10.15
SWEA 5656: 벽돌 깨기 (C++)  (0) 2019.10.14
SWEA 2115: 벌꿀채취 (C++)  (0) 2019.10.14

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

+ Recent posts

티스토리툴바