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

티스토리툴바