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




테스트 케이스 2번의 경우를 잘 처리해야 한다.


그냥 채집할 수 있는 가장 큰 꿀을 그리디하게 채집하게 되면, 7과 5,5 를 비교한다고 했을 때, 


이윤이 5 두개를 채집했을 경우 더 크기 때문에, 결국 모든 경우에 대해서 이윤을 비교하기 위해 완전탐색이 필요함을 알 수 있다.



일단 사람이 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
 
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef pair<int, int> pii;
 
int map[11][11], n, m, c;
 
bool cmp(int a, int b) {
    return a > b;
}
 
struct Info {
    pii pos;
    int pft;
};
 
bool cmpCandi(Info a, Info b) {
    return a.pft > b.pft;
}
 
 
bool vis[11];
vector<int> arr;
 
int tmpMax = -1;
void dfs(int k, int Sum, int bef, vector<int>& tmp) {
    if (Sum >= c || k == m) {
        //최대이윤인지 확인
        
        bool reduce = false;
        if (Sum > c) { //수집 가능한 양을 초과했으면 직전 수집 양을 감소 시켜줘야함
            Sum -= bef;
            reduce = true; //종료 조건에서 arr벡터 pop을 해주면 다른 부분에서 중복 pop이 되기 때문에 이렇게 처리함
        }
 
        int Size = arr.size();
        if (reduce) Size--; //하나 덜 검사하도록 처리
 
        int tmpPft = 0;
        for (int i = 0; i < Size; i++)
            tmpPft = tmpPft + arr[i] * arr[i];
 
        if (tmpMax < tmpPft) tmpMax = tmpPft; //최대 이윤 갱신
        return;
    }
 
 
    for (int i = 0; i < tmp.size(); i++) {
        if (vis[i]) continue;
        vis[i] = true;
        
        arr.push_back(tmp[i]);
        
        dfs(k+1, Sum+tmp[i], tmp[i], tmp);
        vis[i] = false;
        arr.pop_back();
    }
}
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int T;
    cin >> T;
    for (int tc = 1; tc <= T; tc++) {
        cin >> n >> m >> c;
        
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                cin >> map[i][j];
 
        vector<Info> candi; //시작지점, 가능 꿀
 
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= n-m; j++) {
                //시작점 i행j열
                vector<int> tmp;
                for (int k = j; k < j + m; k++) 
                    tmp.push_back(map[i][k]); //꿀 후보 추가
                
                //최대 이윤내는 꿀 골라서 이윤 계산
 
                tmpMax = -1;
        
                dfs(0, 0, 0, tmp); //인덱스, 합, 이전까지합,
 
                Info tmpInfo;
                tmpInfo.pos = { i, j };
                tmpInfo.pft = tmpMax;
                candi.push_back(tmpInfo); //시작지점, 이익 push
                
                tmp.clear();
            }
        }
 
        sort(candi.begin(), candi.end(), cmpCandi);
 
        int Max = -1;
        for (int i = 0; i < candi.size(); i++) {
            for (int j = i + 1; j < candi.size(); j++) {
                if (candi[i].pos.first == candi[j].pos.first) { //같은 칸에서 두명이 채집한 경우 pass
                    if (candi[j].pos.second <= candi[i].pos.second + m - 1 ||
                        candi[i].pos.second <= candi[j].pos.second + m - 1) continue;
                }
                if (candi[i].pft + candi[j].pft > Max) Max = candi[i].pft + candi[j].pft;
 
            }
        }
 
        printf("#%d %d\n", tc, Max);
        candi.clear();
    }
    
    return 0;
}
 
 
cs


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

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

SWEA 2105: 디저트 카페 (C++)  (0) 2019.10.15
SWEA 5656: 벽돌 깨기 (C++)  (0) 2019.10.14
SWEA 1953: 탈주범 검거 (C++)  (0) 2019.10.13
SWEA 5644: 무선 충전 (C++)  (0) 2019.10.09
SWEA 4008번: 숫자 만들기 (C++)  (0) 2019.10.08

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




통로를 통해서 이동을 하는데, 현재의 통로에서 목적지의 통로로 이동할 수 있는지 확인해가며 BFS를 구현해주면 된다.




BFS의 특성상 가까운 지점을 무조건 먼저 방문하게 되므로, 임계 거리를 방문하는 순간 BFS를 종료해주면 된다.




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>
#include<vector>
#include<queue>
using namespace std;
typedef pair<int, int> pii;
 
int m[51][51], dis[51][51];
vector<vector<int> > dr = { {0,0,1,-1}, {1,-1}, {0,0}, {0, -1},{1, 0},{1,0}, {-1,0} }; //동서남북
vector<vector<int> > dc = { {1,-1,0,0}, {0,0}, {1,-1}, {1,0}, {0,1}, {0, -1}, {0,-1} };
 
queue<pii> q;
 
int r, c, mr, mc, Time; //m~ 맨홀 위치
int cnt = 0;
 
int findDir(int nr, int nc) {
    if (nr == 0 && nc == 1) return 1;
    else if (nr == 0 && nc == -1) return 2;
    else if (nr == 1 && nc == 0) return 3;
    else return 4;
}
 
bool dirCheck(int srcDir, int desIdx) {
    if (srcDir == 1) { //동쪽으로 이동중인 경우
        if (desIdx == 2 || desIdx == 4 || desIdx == 5) return false;
        else return true;
    }
    else if (srcDir == 2) { //서쪽으로 이동중인 경우
        if (desIdx == 2 || desIdx == 6 || desIdx == 7) return false;
        else return true;
    }
    else if (srcDir == 3) { //남쪽으로 이동중인 경우
        if (desIdx == 3 || desIdx == 5 || desIdx == 6) return false;
        else return true;
    }
    else { //북쪽으로 이동중인 경우
        if (desIdx == 3 || desIdx == 4 || desIdx == 7) return false;
        else return true;
    }
}
 
void bfs(pii st) {
    q.push(st);
    dis[st.first][st.second]++; //시작점 시간 1로
    cnt++;
    
    while (!q.empty()) {
        pii cur = q.front();
        q.pop();
        if (dis[cur.first][cur.second] >= Time) return; //탈출조건
 
        int deltaIdx = m[cur.first][cur.second]; //1나오면 0으로 써야함(좌표 이동 벡터 인덱스)
        
        for (int i = 0; i < dr[deltaIdx - 1].size(); i++) {
            int nr = cur.first + dr[deltaIdx - 1][i];
            int nc = cur.second + dc[deltaIdx - 1][i];
 
            if (nr < 0 || nc < 0 || nr >= r || nc >= c || dis[nr][nc] >= 1) continue;
            if (m[nr][nc] == 0) continue;
 
            int curDir = findDir(dr[deltaIdx - 1][i], dc[deltaIdx - 1][i]); //어느 방향으로 이동중인지
            
            
            if (!dirCheck(curDir, m[nr][nc])) continue; //이동할 수 없는 방향
 
            q.push({ nr, nc });
            dis[nr][nc] = dis[cur.first][cur.second] + 1;
 
            cnt++;
        }
    }
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int T;
    cin >> T;
    for (int tc = 1; tc <= T; tc++) {
 
        cin >> r >> c >> mr >> mc >> Time;
        
        for (int i = 0; i < r; i++)
            for (int j = 0; j < c; j++)
                cin >> m[i][j]; 
        
        bfs({ mr, mc });
        
        printf("#%d %d\n", tc, cnt);
 
        //초기화
        cnt = 0;
        while (!q.empty()) q.pop();
        for (int i = 0; i < r; i++)
            for (int j = 0; j < c; j++)
                dis[i][j] = 0;
    }
    return 0;
}
 
 
cs


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

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

SWEA 5656: 벽돌 깨기 (C++)  (0) 2019.10.14
SWEA 2115: 벌꿀채취 (C++)  (0) 2019.10.14
SWEA 5644: 무선 충전 (C++)  (0) 2019.10.09
SWEA 4008번: 숫자 만들기 (C++)  (0) 2019.10.08
SWEA 1952: 수영장 (C++)  (0) 2019.10.04

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



사용할 수 있는 연산자의 개수를 하나씩 감소시켜보면서 DFS를 수행해주면된다.


사용중 처리를 연산자의 수를 조절해줌으로써 해준다.



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
#include<vector>
#include<iostream>
#include<set>
#include<climits>
using namespace std;
int n;
long long Min = LONG_MAX;
long long Max = LONG_MAX * -1;
vector<int> opr;
vector<int> arr;
 
set<vector<int> > st;
int num[13];
bool used[13];
 
void pick(int k) {
    if (k == n - 1) {
        long long res = num[0];
        for (int i = 0; i < arr.size(); i++) {
            int cmd = arr[i];
 
            if (cmd == 0)
                res += num[i + 1];
            else if (cmd == 1)
                res -= num[i + 1];
            else if (cmd == 2)
                res *= num[i + 1];
            else
                res /= num[i + 1];
        }
 
        if (res < Min) Min = res;
        if (res > Max) Max = res;
        //st.insert(arr);
        return;
    }
    
 
    for (int i = 0; i < 4; i++) {
        if (opr[i] > 0) {
            arr[k] = i;
            opr[i]--;
            pick(k + 1);
            opr[i]++;
        }
    }
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int T;
    cin >> T;
    
    for (int tc = 1; tc <= T; tc++) {
        cin >> n;
 
        //더하기, 뺴기, 곱하기, 나누기
        for (int i = 0; i < 4; i++) {
            int cnt;
            cin >> cnt;
            
            opr.push_back(cnt);
        }
        for (int i = 0; i < n; i++)
            cin >> num[i];
    
        for (int i = 0; i < n - 1; i++)
            arr.push_back(0);
 
        pick(0);
        
 
        long long dif = Max - Min;
        if (dif < 0) dif *= -1;
        cout << "#" << tc << ' ' << dif << '\n';
 
        Min = LONG_MAX;
        Max = LONG_MAX * -1;
        opr.clear();
        st.clear();
        arr.clear();
    }
    return 0;
}
 
 
cs


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

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

SWEA 1953: 탈주범 검거 (C++)  (0) 2019.10.13
SWEA 5644: 무선 충전 (C++)  (0) 2019.10.09
SWEA 1952: 수영장 (C++)  (0) 2019.10.04
SWEA 4013번: 특이한 자석 (C++)  (0) 2019.10.03
SWEA 4012번: 요리사 (C++)  (0) 2019.10.03

모든 경우에 대해서 완전 탐색을 해주면 된다.


결정하는 달에 이용 내역이 없으면 비용 추가 없이(이용권 구매 없이) 다음 달로 넘어간다.



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
#include<iostream>
#define INF 987654321;
using namespace std;
 
int price[4], plan[15], Min = INF;
 
void dfs(int month, int fee) {
    if (month >= 12) {
        if (fee < Min) Min = fee;
        
        return;
    }
    
    //(month + 1)월 어떻게 낼건지 결정
 
    if (plan[month + 1] == 0) //그 달에 이용 내역이 없으면 비용 추가 없이 월 추가
        dfs(month + 1, fee);
    
    else {
        dfs(month + 1, fee + price[0] * plan[month + 1]); //1일
        dfs(month + 1, fee + price[1]); //1달
        dfs(month + 3, fee + price[2]); //3달
    }
}
 
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 = 0; i < 4; i++)
            cin >> price[i]; // 1일, 1달, 3달 1년
        
        
        for (int i = 1; i <= 12; i++)
            cin >> plan[i];
        
        if (Min > price[3]) Min = price[3]; // 1년치
        
        dfs(0, 0);
        cout << "#" << tc << ' ' <<  Min << '\n';
        Min = INF; //Min 초기화
    }
    return 0;
}
 
 
cs


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

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

SWEA 5644: 무선 충전 (C++)  (0) 2019.10.09
SWEA 4008번: 숫자 만들기 (C++)  (0) 2019.10.08
SWEA 4013번: 특이한 자석 (C++)  (0) 2019.10.03
SWEA 4012번: 요리사 (C++)  (0) 2019.10.03
SWEA 1244번: 최대 상금 (C++)  (2) 2019.09.27

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://swexpertacademy.com/main/code/problem/problemList.do?problemTitle=SW&orderBy=PASS_RATE&select-1=&pageSize=10&pageIndex=1#none



음식 하나에 들어가는 재료는 n/2개이다. 조합을 이용해서 음식 하나에 들어갈 수 있는 재료를 뽑는다.


여기서 뽑힌 재료가 음식 하나에 들어가는 재료가 되는 것이고, 뽑히지 않은 재료는 나머지 음식에  들어가는 재료가 된다.



뽑은 재료들 사이에 시너지를 계산하기 위해서, 순열로 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
#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
#define INF 987654321
 
int Min = INF;
int food[18][18], arr[2];
int st = 1, n;
bool used[18], usedP[18];
 
vector<int> candi, others;
int Sum = 0;
 
void per(int K, vector<int>& useable) {
    if (K == 2) {
        Sum += food[arr[0]][arr[1]]; //실제로 시너지 계산하는 부분
        return;
    }
    
    for (int i = 0; i < useable.size(); i++) {
        if (!usedP[i]) {
            arr[K] = useable[i];
            usedP[i] = true;
            per(K + 1, useable);
            usedP[i] = false;
        }
    }
}
void com(int k, int goal) {
    if (k == goal) { //n/2개 뽑으면
 
        ////candi에서 2개 순열로 뽑아서 시너지 계산
        Sum = 0;
        per(0, candi);
        int sumA = Sum;
        
        
        //다른 음식에 쓰이는 재료도 마찬가지로 시너지 계산
        others.clear();
        for (int i = 1; i <= n; i++) 
            if (!used[i]) others.push_back(i);
        
 
        Sum = 0;
        per(0, others);
        int sumB = Sum;
 
        int dif = abs(sumA - sumB);
        if (dif < Min) Min = dif; //맛의 차이 업데이트
 
        return;
    }
 
    if (k == 0) st = 1;
    for (int i = st; i <= n; i++) {
        if (!used[i]) {
            st = i;
            used[i] = true;
            candi.push_back(i); //음식 하나에 쓰일 재료에 추가
            com(k + 1, goal);
            used[i] = false;
            candi.pop_back();
        }
    }
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    for (int tc = 1; tc <= T; tc++) {
        
        cin >> n;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                cin >> food[i][j];
        
        com(0, n / 2); //절반을 조합으로 뽑는다(음식 하나에 쓰일 재료 선택)
 
        cout << "#" << tc << ' ' << Min << '\n';
        Min = INF;
        candi.clear();
        
    }
 
    return 0;
}
 
 
cs



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

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

SWEA 1952: 수영장 (C++)  (0) 2019.10.04
SWEA 4013번: 특이한 자석 (C++)  (0) 2019.10.03
SWEA 1244번: 최대 상금 (C++)  (2) 2019.09.27
SWEA 3752번: 가능한 시험 점수 (C++)  (0) 2019.09.27
SWEA 2814: 최장 경로 (C++)  (0) 2019.09.25

주어지는 수의 모든 자리에 대해서 숫자를 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
 
#include<iostream>
#include<string>
 
using namespace std;
 
string org, tmp;
int n; //n번 스왑
int Max;
void dfs(int here, int cnt) { //인덱스 here과 바꿀곳 검색
    if (cnt == n) {
        int candi = stoi(org);
        if (Max < candi) Max = candi;
 
        return;
    }
    
    for (int i = here; i < org.length(); i++) {
        for (int j = i + 1; j < org.length(); j++) {
            if (org[i] <= org[j]) { //수가 작아지지 않도록
                int temp = org[i];
                org[i] = org[j];
                org[j] = temp;
                
                dfs(i, cnt + 1);
 
                temp = org[i];
                org[i] = org[j];
                org[j] = temp;
            }
        }
    }
}
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    for (int tc = 1; tc <= T; tc++) {
        cin >> org >> n;
        Max = stoi(org);
        dfs(0, 0);
        cout << '#'<<tc<< ' ' << Max << '\n';
    }
    return 0;
}
 
 
cs



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

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

SWEA 1952: 수영장 (C++)  (0) 2019.10.04
SWEA 4013번: 특이한 자석 (C++)  (0) 2019.10.03
SWEA 4012번: 요리사 (C++)  (0) 2019.10.03
SWEA 3752번: 가능한 시험 점수 (C++)  (0) 2019.09.27
SWEA 2814: 최장 경로 (C++)  (0) 2019.09.25

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



0점은 무조건 받을 수 있기 때문에 초기에 백터에 0을 넣어준다.


이후에 문제의 배점별 점수를 받으면서, 백터에 존재하는 점수와 더해주고,


더해진 점수가 그 백터에 들어있지 않다면 점수를 추가해준다.


더해지는 점수가 백터에 포함되어 있는지 매번 백터를 돌면서 확인하지 않기 위해 숫자를 사용했는지 여부를


담는 배열을 만들어서 확인한다.



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
#pragma warning(disable :4996)
#include<iostream>
#include<vector>
using namespace std;
bool vis[10001]; //최대 만점
int n;
vector<int> v;
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    
    for (int tc = 1; tc <= T; tc++) {
        cin >> n;
        
        v.push_back(0);
        vis[0] = true;
        int val;
        for (int i = 0; i < n; i++) {
            cin >> val;
            int curSize = v.size(); //새로운 숫자 넣기 직전에 백터 크기
            for (int j = 0; j < curSize; j++) {
                int candi = val + v[j]; //추가될 수 있는 수
                if (!vis[candi]) { //이미 추가된 수면 pass
                    v.push_back(candi);
                    vis[candi] = true;
                }
            }
        }
        cout  << '#' << tc << ' ' << v.size() << '\n';
        v.clear();
        for (int i = 0; i <= 10000; i++)
            vis[i] = false;
    }
    
    return 0;
}
cs


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

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

SWEA 1952: 수영장 (C++)  (0) 2019.10.04
SWEA 4013번: 특이한 자석 (C++)  (0) 2019.10.03
SWEA 4012번: 요리사 (C++)  (0) 2019.10.03
SWEA 1244번: 최대 상금 (C++)  (2) 2019.09.27
SWEA 2814: 최장 경로 (C++)  (0) 2019.09.25

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



모든 정점을 시작점으로 dfs를 돌려주면 된다.



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
#include<iostream>
 
using namespace std;
 
int grp[11][11]; //1-indexed
bool vis[11]; //방문처리
int n, m, Max = 1;
 
void dfs(int len, int cur) {
    vis[cur] = true;
 
    if (Max < len) Max = len;
    for (int i = 1; i <= n; i++) {
        if (grp[cur][i] == 1 && !vis[i])
            dfs(len + 1, i);
    }
    vis[cur] = false;
}
 
void initGrp() {
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            grp[i][j] = 0;
}
 
int main(void) {
 
    int T;
    cin >> T;
    for (int tc = 1; tc <= T; tc++) {
        
        cin >> n >> m;
        
        for (int i = 0; i < m; i++) {
            int src, dst;
            cin >> src >> dst;
            
            grp[src][dst] = 1;
            grp[dst][src] = 1;
            
        }
 
        for (int i = 1; i <= n; i++) 
            dfs(1, i); // i번 정점에서 길이 
        
        printf("#%d %d\n", tc, Max);
        Max = 1;
        initGrp();
    }
 
    return 0;
}
cs




방문 처리를 조금 더 직관적으로 하면 다음과 같이 구현할 수 있다.




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>
 
using namespace std;
 
int grp[11][11]; //1-indexed
bool vis[11]; //방문처리
int n, m, Max = 1;
 
void dfs(int len, int cur) {
    //vis[cur] = true;
 
    if (Max < len) Max = len;
    for (int i = 1; i <= n; i++) {
        if (grp[cur][i] == 1 && !vis[i]) {
            vis[i] = true;
            dfs(len + 1, i);
            vis[i] = false;
        }
    }
    //vis[cur] = false; //확인이 끝난 점은 방문을 해제
}
 
void initGrp() {
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            grp[i][j] = 0;
}
 
int main(void) {
 
    int T;
    cin >> T;
    for (int tc = 1; tc <= T; tc++) {
        
        cin >> n >> m;
        
        for (int i = 0; i < m; i++) {
            int src, dst;
            cin >> src >> dst;
            
            grp[src][dst] = 1;
            grp[dst][src] = 1;
            
        }
 
        for (int i = 1; i <= n; i++) {
            vis[i] = true;
            dfs(1, i); // i번 정점에서 길이
            vis[i] = false;
        }
        
        printf("#%d %d\n", tc, Max);
        Max = 1;
        initGrp();
    }
 
    return 0;
}
cs


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

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

SWEA 1952: 수영장 (C++)  (0) 2019.10.04
SWEA 4013번: 특이한 자석 (C++)  (0) 2019.10.03
SWEA 4012번: 요리사 (C++)  (0) 2019.10.03
SWEA 1244번: 최대 상금 (C++)  (2) 2019.09.27
SWEA 3752번: 가능한 시험 점수 (C++)  (0) 2019.09.27

+ Recent posts

티스토리툴바