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

+ Recent posts

티스토리툴바