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

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




연산자의 수가 가령 1,5,0,3


이렇게 주어지면 나는 새로운 벡터에 0을 1개, 1을 5개, 3을 3개 추가하고, 그 백터를 이용해서 순열을 돌렸다.


이 과정에서 중복도 발생하고, set을 사용해서 중복을 처리해주더라도 연산 시간이 소모되기 때문에 시간초과가 나는 것 같다.



따라서, 그냥 1,5,0,3 상태에서, 내가 무언가를 뽑으면 그 원소에 1을 더하거나 빼주고, 양수일 경우에만 뽑을 수 있게 하는 방식으로 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
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<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 < opr.size(); i++) {
        if (!used[i]) {
 
            //arr.push_back(opr[i]);
            arr[k] = opr[i];
            used[i] = true;
            pick(k + 1);
            used[i] = false;
            //arr.pop_back();
        }
    }
}
void process() {
 
    for (set<vector<int> > ::iterator itr = st.begin(); itr != st.end(); itr++) {
        vector<int> cur = *itr;
    /*    long long res = num[0];
        for (int i = 0; i < cur.size(); i++) 
            res = cal(res, cur[i], num[i + 1]);*/
        
        long long res = num[0];
        for (int i = 0; i < cur.size(); i++) {
            int cmd = cur[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;
    }
 
}
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;
            while (cnt--) {
                opr.push_back(i);
            }
        }
        for (int i = 0; i < n; i++)
            cin >> num[i];
    
        for (int i = 0; i < n - 1; i++)
            arr.push_back(0);
 
        pick(0);
        //process();
 
        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


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

'알고리즘 문제 풀이 > 오답' 카테고리의 다른 글

백준 2251번: 물통 (C++)  (0) 2019.08.31
백준 1525번: 퍼즐 (C++)  (0) 2019.08.30
연산자 우선 순위가 없는 경우 +, -, * 연산 구현  (0) 2019.08.21
[오답] 카카오 2018 블라인드 테스트: 무지의 먹방 라이브 C++  (0) 2019.08.20
[오답] 백준 1941 소문난 칠공주 C++  (0) 2019.08.10

퀵소트: 

평균 nlogn, 

최악 n^2(데이터가 이미 거의 정렬되어 있는 경우)



머지소트: 

평균: nlogn보장

단점: 메모리 비효율적이라는 문제-> 힙소트로 해결



힙소트:

일단 데이터를 가지고 힙구조를 만들어야함. 이 부분의 복잡도 == NlogN

그리고, 루트의 값을 맨 뒤로 보내면서, 보낸 값을 제외하고 다시 힙을 만드는 비용이 logN. 이걸 N번 반복하니까 NlogN

결국 합치면 총 시간 복잡도는 NlogN이 된다.

장점: 메모리 효율적.


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

'Computer Science > Algorithm Theory' 카테고리의 다른 글

C++ 알고리즘 체크리스트  (0) 2021.10.16
삽입 정렬 알고리즘 구현 (C++)  (0) 2019.08.28
버블 정렬 알고리즘 구현 (C++)  (0) 2019.08.28
선택 정렬 알고리즘 구현 (C++)  (0) 2019.08.28
Counting Sort (C++)  (0) 2019.08.23

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


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



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

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



선거구가 형성될 수 있는 조건은 선거구에 구역이 1개 이상 포함되는 것이다.



따라서 조합을 이용해서, 주어지는 n개의 구역 중에서 1개 이상 뽑는 경우에 대해서 처리해주면 된다.


단, n개를 뽑게 되면, 다른 선거구에 속하는 구역이 0개가 된다는 의미이므로 n개 뽑는 경우는 제외해준다.




구역을 적절하게 뽑았다면 다음과 같은 처리를 해준다.


우선 n <= 10 으로 작기 때문에 2차원 bool 배열에 구역의 연결 관계를 인접행렬로 나타내준다.


그리고 처음에 뽑은 구역들이 선거구를 이룰 수 있는지(모두 연결되어 있는지) 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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include<iostream>
#include<queue>
#include<cmath>
#include<vector>
using namespace std;
 
int n, pop[11], tot = 0, Min = 987654321, st = 1;
bool vis[11], map[11][11], used[11];
queue<int> q;
 
int bfs(int st, bool usedCheck) { //true인 경우가 처음 뽑은 구역들 연결 확인하는 경우
    q.push(st);
    vis[st] = true;
    int restSum = pop[st];
    
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        for (int i = 1; i <= n; i++) {
            if (usedCheck)
                if (!used[i]) continue; //뽑은 곳들에 대해서만 연결 관계 확인
            
            if (!map[cur][i] || vis[i]) continue;
            
            q.push(i);
            vis[i] = true;
            restSum += pop[i];
        }
    }
    return restSum; //선거구 인원 반환
}
 
void process() {
    int pickedSum, restSum;
    
 
    //처음에 뽑은 게 모두 연결되어 있는지 확인
    for (int i = 1; i <= n; i++) {
        if (used[i]) {
            pickedSum = bfs(i, true);
            break;
        }
    }
 
    bool firCon = true;
    for (int i = 1; i <= n; i++) {
        if (used[i]) { //뽑은 것중에
            if (!vis[i]) firCon = false; //연결 안 된거 하나라도 있으면 거르기
        }
    }
 
    for (int i = 1; i <= n; i++) //방문 처리 배열 초기화
        vis[i] = false;
 
    if (!firCon) return;
 
 
    for (int i = 1; i <= n; i++) 
        if (used[i]) vis[i] = true; //확정된 선거구 방문처리
    
    for(int i = 1; i <= n; i++) {
        if (!vis[i]) {
            restSum = bfs(i, false); //나머지 선거구 인원 계산 + 연결 관계 확인
            break;
        }
    }
 
    bool allCon = true;
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) { //선거구 형셩 불가
            allCon = false;
            break;
        }
    }
    
    if(allCon) {
        int dif = abs(tot - restSum - restSum);
        if (Min > dif) Min = dif;
    }
    for (int i = 1; i <= n; i++)
        vis[i] = false;
}
void btk(int cnt) {
    if (cnt >= 1) {
        if (cnt >= 6) return;
        //전부 다 뽑은 경우 제외
        process();
    }
    
    if (cnt == 0) st = 1;
    for (int i = st; i <= n; i++) {
        if (!used[i]) {
            st = i;
            used[i] = true;
            btk(cnt + 1);
            used[i] = false;
        }
    }
}
 
int main(void) {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> pop[i];
        tot += pop[i];
    }
 
    for (int i = 1; i <= n; i++) {
        int edgeCnt;
        cin >> edgeCnt;
        while (edgeCnt--) {
            int dst;
            cin >> dst;
            map[dst][i] = true;
            map[i][dst] = true;
        }
    }
 
    btk(0);
 
    if (Min == 987654321) cout << -1;
    else
        cout << Min;
 
    return 0;
}
cs


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

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

백준 1717번: 집합의 표현(C++)  (0) 2021.10.06
백준 17472번: 다리만들기2 (C++)  (0) 2019.10.19
백준 13549번: 숨바꼭질 3 (C++)  (0) 2019.09.27
백준 3055번: 탈출 (C++)  (0) 2019.09.27
백준 9935번: 문자열 폭발 (C++)  (0) 2019.09.26

https://www.welcomekakao.com/learn/courses/30/lessons/43163



단어의 철자를 바꿔가면서 목록에 있는 단어들 사이에서 차례로 변화가 일어날 수 있다는 것을 이용해서


인접행렬을 만들어준다.


초기 시작지점을 찾을 때, 단어를 바꾸고 시작하냐, 수정 없이 시작하냐를 따져준다.


목적 단어가 목록에 없으면 BFS를 수행할 필요도 없이 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
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
#include <string>
#include <vector>
#include<iostream>
#include<queue>
using namespace std;
 
int m[51][51], dis[51], st = -1, en = -1;
bool addOne = false;
queue<int> q;
void bfs(vector<string>& grp) {
    q.push(st);
    dis[st]++;
    while (!q.empty()) {
        int qs = q.size();
        while (qs--) {
            int cur = q.front();
            q.pop();
 
            for (int i = 0; i < grp.size(); i++) {
                if (m[cur][i] == 0 || dis[i] >= 0) continue;
                q.push(i);
                dis[i] = dis[cur] + 1;
                if (i == en) return;
            }
        }
    }
}
int solution(string src, string dst, vector<string> wrds) {
 
    int len = wrds[0].length();
 
    for (int i = 0; i < wrds.size(); i++) {
        dis[i] = -1;
        if (wrds[i] == src) { //시작 단어와 같은 단어가 목록에 존재
            st = i;
            addOne = false; //결과에 1 더해줄 필요가 없음
        }
        if (wrds[i] == dst) en = i;
 
        if (st == -1) { //시작 단어와 같은 단어가 목록에 없는 경우
            int dif = 0;
            for (int k = 0; k < len; k++) {
                if (wrds[i][k] != src[k]) dif++;
                if (dif > 1) break;
            }
            if (dif == 1) {
                st = i;
                addOne = true; //결과에 1을 더해준다. 시작부터 한번 바꾸고 시작했으니까
            }
        }
 
        //단어를 노드로 인접행렬 만들기
        for (int j = i + 1; j < wrds.size(); j++) {
            int dif = 0;
            for (int k = 0; k < len; k++) {
                if (wrds[i][k] != wrds[j][k]) dif++;
                if (dif > 1) break;
            }
            if (dif == 1) { //철자 하나 다를때만 연결
                m[i][j] = 1;
                m[j][i] = 1;
            }
        }
    }
 
    //목표 단어가 목록에 없으면 0 반환
    if (en != -1)
        bfs(wrds);
    else return 0;
 
    if (dis[en] != -1) { //바꿀 수 있으면
        if (!addOne)
            return dis[en];
        else
            return dis[en] + 1;
    }
    else
        return 0;
}
cs


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

'알고리즘 문제 풀이 > 프로그래머스' 카테고리의 다른 글

프로그래머스: 메뉴 리뉴얼 (C++)  (0) 2021.08.22
프로그래머스: 베스트앨범 (C++)  (0) 2019.10.30
프로그래머스: 네트워크 (C++)  (0) 2019.09.28
프로그래머스: 카펫 (C++)  (0) 2019.09.28
프로그래머스: 숫자 야구 (C++)  (0) 2019.09.27

https://www.welcomekakao.com/learn/courses/30/lessons/43162


DFS혹은 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
#include <string>
#include <vector>
 
using namespace std;
bool vis[201];
void dfs(int here, vector<vector<int>> &grp) {
    
    vis[here] = true;
    
    for (int i = 0; i < grp[here].size(); i++) {
        if (grp[here][i] == 0 || vis[i]) continue;
        dfs(i, grp);
    }
}
int solution(int n, vector<vector<int>> coms) {
    
    int ans = 0;
    for (int i = 0; i < coms.size(); i++) {
        if (!vis[i]) {
            ans++;
            dfs(i, coms);
        }
    }
    return ans;
 
    return 1;
}
 
cs


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

'알고리즘 문제 풀이 > 프로그래머스' 카테고리의 다른 글

프로그래머스: 베스트앨범 (C++)  (0) 2019.10.30
프로그래머스: 단어 변환 (C++)  (0) 2019.09.29
프로그래머스: 카펫 (C++)  (0) 2019.09.28
프로그래머스: 숫자 야구 (C++)  (0) 2019.09.27
프로그래머스: 소수찾기 (C++)  (0) 2019.09.27

+ Recent posts

티스토리툴바