- Problem
- [1] Answer Code (18. 08. 31)
- [2] Wrong Code (18. 08. 31)
- [3] Answer Code (18. 06. 01)
- [4] Answer Code (18. 04. 01)
Problem
Problem URL : 미생물 격리
[1] Answer Code (18. 08. 31)
#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
struct Bug {
int x;
int y;
int cnt;
int dir;
Bug(int x,int y,int cnt, int dir):x(x),y(y),cnt(cnt),dir(dir){}
};
int map[101][101];
int change_dir[] = {0,2,1,4,3};
pair<int,int> max_bug[101][101];
int main(){
int TC;
cin >> TC;
for (int tc=1; tc<=TC; tc++) {
int n,m,k; // 셀의 개수 N, 격리 시간 M, 미생물 군집의 개수 K
cin >> n >> m >>k ;
memset(max_bug,0,sizeof(max_bug));
vector<Bug> bug;
for(int i=0; i<k; i++){
int a,b,c,d;
cin >> a >> b >> c >> d;
bug.push_back(Bug(a,b,c,d));
}
while (m--) {
memset(map,-1,sizeof(map));
// Bug Move
for(int i=0; i<k; i++){
if(bug[i].cnt == 0) continue;
if(bug[i].dir == 1) bug[i].x -= 1;
else if(bug[i].dir == 2) bug[i].x += 1;
else if(bug[i].dir == 3) bug[i].y -= 1;
else if(bug[i].dir == 4) bug[i].y += 1;
// 가장 자리일 경우
if( bug[i].x == 0 || bug[i].x == n-1 || bug[i].y == 0 || bug[i].y == n-1){
bug[i].cnt /= 2;
bug[i].dir = change_dir[bug[i].dir];
map[ bug[i].x ][ bug[i].y ] = i;
}
// 이동한 장소에 이미 있을 시
else if(map[ bug[i].x ][ bug[i].y ] != -1){
// 해당 좌표에 존재하는 Bug의 Index
int pre_bug_idx = map[ bug[i].x ][ bug[i].y ];
if( max_bug[ bug[i].x ][ bug[i].y ].first > bug[i].cnt){
bug[pre_bug_idx].cnt += bug[i].cnt;
bug[i].cnt = 0;
}
else{
max_bug[ bug[i].x ][ bug[i].y ] = {bug[i].cnt, bug[i].dir}; // [1]
bug[i].cnt += bug[pre_bug_idx].cnt;
bug[pre_bug_idx].cnt = 0;
map[ bug[i].x ][ bug[i].y ] = i; // map에 새로운 bug index로 초기화
// max_bug[ bug[i].x ][ bug[i].y ] = {bug[i].cnt, bug[i].dir}; // [2]
}
} // end of else if
else{
map[ bug[i].x ][ bug[i].y ]= i;
max_bug[ bug[i].x ][ bug[i].y ] = {bug[i].cnt, bug[i].dir};
}
} // end of for i
} // end of while
int ans = 0;
for(int i=0; i<k; i++){
ans += bug[i].cnt;
}
printf("#%d %d\n",tc, ans);
} // end of for tc
return 0;
}
Reivew
- 으아아아아아 [2]에 두고 하니까 자꾸 틀렸다. [1]으로 옮기니까 맞네
너무 오래 걸렸다. 반성해야겠다.
[2] Wrong Code (18. 08. 31)
#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
struct Bug {
int x;
int y;
int cnt;
int dir;
Bug(int x,int y,int cnt, int dir):x(x),y(y),cnt(cnt),dir(dir){}
};
int map[100][100];
int change_dir[] = {0,2,1,4,3};
int main(){
int TC;
cin >> TC;
for (int tc=1; tc<=TC; tc++) {
int n,m,k; // 셀의 개수 N, 격리 시간 M, 미생물 군집의 개수 K
cin >> n >> m >>k ;
vector<Bug> bug;
for(int i=0; i<k; i++){
int a,b,c,d;
cin >> a >> b >> c >> d;
bug.push_back(Bug(a,b,c,d));
}
while (m--) {
memset(map,-1,sizeof(map));
// Bug Move
for(int i=0; i<k; i++){
if(bug[i].cnt == 0) continue;
if(bug[i].dir == 1) bug[i].x -= 1;
else if(bug[i].dir == 2) bug[i].x += 1;
else if(bug[i].dir == 3) bug[i].y -= 1;
else if(bug[i].dir == 4) bug[i].y += 1;
// 가장 자리일 경우
if( bug[i].x == 0 || bug[i].x == n-1 || bug[i].y == 0 || bug[i].y == n-1){
bug[i].cnt /= 2;
bug[i].dir = change_dir[bug[i].dir];
map[ bug[i].x ][ bug[i].y ] = i;
}
// 이동한 장소에 이미 있을 시
else if(map[ bug[i].x ][ bug[i].y ] != -1){
// 해당 좌표에 존재하는 Bug의 Index
int pre_bug_idx = map[ bug[i].x ][ bug[i].y ];
if( bug[pre_bug_idx].cnt > bug[i].cnt){
bug[pre_bug_idx].cnt += bug[i].cnt;
bug[i].cnt = 0;
// cout << pre_bug_idx << " take " << i << endl;
}
else{
bug[i].cnt += bug[pre_bug_idx].cnt;
bug[pre_bug_idx].cnt = 0;
// map에 새로운 bug index로 초기화
map[ bug[i].x ][ bug[i].y ] = i;
// cout << i << " take " << pre_bug_idx << endl;
}
} // end of else if
else{
map[ bug[i].x ][ bug[i].y ]= i;
}
} // end of for i
} // end of while
int ans = 0;
for(int i=0; i<k; i++){
ans += bug[i].cnt;
}
printf("#%d %d\n",tc, ans);
} // end of for tc
return 0;
}
Review
-
로직구현은 30분안에 해서 코딩까지 빠른 시간내에 했는데 틀렸다.
-
처음엔 memset(map,-1,sizeof(map)); 이 부분을 놓쳤다
그리고 도저히 모르겠어서 질문을 남겼는데 굉장히 단순한 실수였다. 그게 내 실력이지만… ㅠㅠ -
다음처럼 입력이 주어질 때 1,2번째 미생물이 합쳐지면서 원래는 3번째 미생울 집단의 3(좌)방향으로 가야하는데
1,2번째 미생물이 먼저 합쳐지고 미생물 수도 많기 때문에 4(우)방향으로 진행이 된다.
1
7 3 3
1 1 120 4
2 2 100 1
1 3 150 3
[3] Answer Code (18. 06. 01)
#include<iostream>
#include<cstring>
#define p pair<int,int>
using namespace std;
p map[2][100][100];
p max_node[100][100];
int n,m,k;
int ans;
int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};
int edgeDir[] = {2,1,4,3};
p changeDir(int x, int y,int dir){
if(dir == 1)
return p(x+dx[3], y+dy[3]);
else if(dir == 2)
return p(x+dx[1], y+dy[1]);
else if(dir == 3)
return p(x+dx[2], y+dy[2]);
else
return p(x+dx[0], y+dy[0]);
}
int main(){
int T;
cin >> T;
for(int i=1; i<=T; i++){
memset(map,0,sizeof(map));
memset(max_node,0,sizeof(max_node));
cin >> n >> m >> k;
ans = 0;
for(int j=0; j<k; j++){
int x,y,cnt,dir;
scanf("%d%d%d%d",&x,&y,&cnt,&dir);
map[0][x][y] = make_pair(cnt, dir);
}
bool flag = true;
while(m--){
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
if(map[!flag][i][j].first != 0){ // 미생물이 있다.
int cnt = map[!flag][i][j].first;
int dir = map[!flag][i][j].second;
p _dir = changeDir(i,j, dir);
int nx = _dir.first;
int ny = _dir.second;
// 가장자리
if( nx == 0 || nx == n-1 || ny == 0 || ny == n-1){
map[flag][nx][ny] = p( cnt >> 1, edgeDir[dir-1]);
}
// 중복될 경우
else if(map[flag][nx][ny].first != 0){
if( max_node[nx][ny].first < map[!flag][i][j].first){
max_node[nx][ny].first = map[!flag][i][j].first; // [1]
max_node[nx][ny].second = map[!flag][i][j].second;
}
map[flag][nx][ny].first += map[!flag][i][j].first;
map[flag][nx][ny].second = max_node[nx][ny].second;
}
else{ // 중복 X
max_node[nx][ny] = map[flag][nx][ny] = p(cnt,dir);
}
map[!flag][i][j] = p(0,0);
}
}
} // End of For i
flag = !flag;
} // End of While
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
if(map[!flag][i][j].first != 0)
ans += map[!flag][i][j].first;
}
}
printf("#%d %d\n",i,ans);
}
return 0;
}
Reivew
-
[SW Expert Academy] 문제.
-
[1] Code 때문에 틀렸었다.
-
확실히 처음풀었을 때 보다 코드는 간결해졌다.
[4] Answer Code (18. 04. 01)
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
struct Node{ // [1]
int x;
int y;
int num;
int dir;
};
int dx[] = {0,-1,1,0,0};
int dy[] = {0,0,0,-1,1};
vector<int> map[100][100]; // [2]
int main(){
int tc;
cin >> tc;
for(int i=1; i<=tc; i++){
int n,m,k;
cin >> n >> m >> k;
vector<Node> v(k); // [3]
for(int i=0; i<k; i++){
cin >> v[i].x >> v[i].y >> v[i].num >> v[i].dir; // [4]
map[v[i].x][v[i].y].push_back(i);
}
while (m--) {
for(int i=0; i<k; i++){
if( v[i].num == 0) continue;
map[v[i].x][v[i].y].clear();
}
for(int i=0; i<k; i++){
if( v[i].num == 0) continue;
v[i].x += dx[ v[i].dir ];
v[i].y += dy[ v[i].dir ];
map[v[i].x][v[i].y].push_back(i);
}
// Check Condition
// 1. Check whether it is located at the edge
// 2. Check for duplicates
for(int i=0; i<k; i++){
if( v[i].num == 0) continue;
if( v[i].x == 0 || v[i].x == n-1 || v[i].y == 0 || v[i].y == n-1){ // [5]
v[i].num /= 2;
if( v[i].dir == 1 ) v[i].dir = 2;
else if( v[i].dir == 2) v[i].dir = 1;
else if( v[i].dir == 3) v[i].dir = 4;
else if( v[i].dir == 4) v[i].dir = 3;
}
else if( map[v[i].x][v[i].y].size() > 1 ){
int max_idx = 0;
int max_num = 0;
int max_dir = 0;
int sum = 0;
int size = (int)map[v[i].x][v[i].y].size();
for(int j=0; j<size; j++){
sum += v[map[v[i].x][v[i].y][j]].num;
if( v[map[v[i].x][v[i].y][j]].num > max_num ){
max_idx = map[v[i].x][v[i].y][j];
max_dir = v[map[v[i].x][v[i].y][j]].dir;
max_num = v[map[v[i].x][v[i].y][j]].num;
}
v[map[v[i].x][v[i].y][j]].num = 0;
}
v[max_idx].num = sum;
v[max_idx].dir = max_dir;
} // End of else if
} // End of for Loop
} // End of While Loop
int ans = 0;
for(int i=0; i<k; i++){
ans += v[i].num;
map[v[i].x][v[i].y].clear();
}
printf("#%d %d\n",i,ans);
} // End of For Loop
return 0;
}
Review
-
[SW Expert Academy] 문제.
-
[1], [2], [3], [4] 이런 디테일한 코딩 스킬이 Samsung 코딩 테스트를 위해서 필요한거 같다.
-
많은 시간이 걸렸지만 그 만큼 재밌었고 많이 배웠다.
-
코드가 길어지다보니
{ }구조 파악하는데 시간이 걸렸다.
주석으로 매칭되는 짝을 명시하자 -
[5] : v[i].x == n으로 해서 틀렸다. n인지 n-1인지 조심하자!