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


위 문제를 counting sort로 구현해 봤다.


주어지는 수의 절댓값이 1,000,000 이하이기 때문에 배열의 인덱스를 활용할 때 음수 처리를 위해 1000000을 더해준 인덱스에 저장한다.


1의 갯수는 1000001에 저장되는 것이다. 


따라서 출력할 때, 1000000을 빼고 출력해주면 된다.


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
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int arr[2000001];
bool cmp(int a, int b) {
    return a > b;
}
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    
    for (int i = 0; i < n; i++) {
        int num;
        cin >> num;
        arr[num + 1000000]++; // 저거 뺴고 출력하면 됨
    }
    for (int i = 0; i <= 2000000; i++) {
        while (arr[i]--)
            cout << i - 1000000 << '\n';
    }
    return 0;
}
 
cs


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

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

버블 정렬 알고리즘 구현 (C++)  (0) 2019.08.28
선택 정렬 알고리즘 구현 (C++)  (0) 2019.08.28
최대 공약수 gcd, 최소 공배수 lcm  (0) 2019.08.19
기하 및 그래프 알고리즘 간단 정리  (0) 2019.08.17
선분 교차 판별  (0) 2019.08.11

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



열이든 행이든 연산 하나를 제대로 구현하면, 나머지 하나는 똑같다.


보통 개수를 셀 때, cnt[m[i]]++ 이런 방식으로 세는데, 이 경우에는 1회 이상 등장한 숫자의 개수도 함께 필요하고,


이 수들의 빈도와 수 자체를 가지고 정렬을 해야하기 때문에 다른 방식을 사용했다.



먼저 map을 사용해서 숫자별 개수를 기록했다. 이후에 벡터에 pair 형태로 옮기면서 정렬했다.



주의할 것이, 중간에 R연산을 할 때는 열의 길이가 갱신되고, C연산을 할 때는 행의 길이가 갱신되는데, 따라서 연산을 시작할 당시의 값으로 반복문의 범위를 잡아줘야, 중간에 반복문의 범위가 바뀌는 것을 방지할 수 있다.



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
#include<iostream>
#include<map>
#include<vector>
#include<algorithm>
 
using namespace std;
typedef pair<int, int> pii;
 
int r, c, k, m[101][101], cnt[101], rnum = 3, cnum = 3;
map<int, int> mp;
vector<pii> v;
 
bool cmp(pii a, pii b) {
    if (a.second < b.second) return true;
    else if (a.second == b.second) {
        return a.first < b.first;
    }
    else return false;
}
 
void rOpr() {
    int curC = cnum; //연산 중간에 행길이를 갱신할 것이기 때문에 시작값 저장
    for (int i = 1; i <= rnum; i++) {
        for (int j = 1; j <= curC; j++) {
            if (m[i][j] == 0) continue;
            mp[m[i][j]]++;
        }
        
        for (map<int, int>::iterator itr = mp.begin(); itr != mp.end(); itr++)
            v.push_back({ itr->first, itr->second });
 
        sort(v.begin(), v.end(), cmp);
 
        int vSize = v.size();
        if (v.size() >= 50) vSize = 50; //100개까지만 취하도록
        for (int j = 0; j < vSize; j++) {
            m[i][2*j+1] = v[j].first;
            m[i][2*j+2] = v[j].second;
        }
        
        for (int j = vSize * 2 + 1; j <= curC; j++)
            m[i][j] = 0; // 원래 길이보다 짧아지면, 이전 것을 0으로 만들어줘야 함
 
        if (cnum < vSize * 2) cnum = vSize * 2; //최대 길이 갱신
        
        mp.clear();
        v.clear();
    
    }
}
 
void cOpr() {
    int curR = rnum;
    for (int i = 1; i <= cnum; i++) {
        for (int j = 1; j <= curR; j++) {
            if (m[j][i] == 0) continue;
            mp[m[j][i]]++;
        }
 
        for (map<int, int>::iterator itr = mp.begin(); itr != mp.end(); itr++)
            v.push_back({ itr->first, itr->second });
 
        sort(v.begin(), v.end(), cmp);
 
        int vSize = v.size();
        if (v.size() >= 50) vSize = 50;
        for (int j = 0; j < vSize; j++) {
            m[2 * j + 1][i] = v[j].first;
            m[2 * j + 2][i] = v[j].second;
        }
 
        for (int j = vSize * 2 + 1; j <= curR; j++)
            m[j][i] = 0;
 
        if (rnum < vSize * 2) rnum = vSize * 2;
 
        mp.clear();
        v.clear();
 
    }
}
int main(void) {
    cin >> r >> c >> k;
    for (int i = 1; i <= 3; i++)
        for (int j = 1; j <= 3; j++)
            cin >> m[i][j];
 
    int time = 0;
    for (time = 0; time <= 100; time++) {
    
        if (m[r][c] == k) break; //종료 조건
        if (rnum >= cnum)  //r연산
            rOpr();
        
        else 
            cOpr();
    }
 
    if (time == 101) cout << -1;
    else cout << time;
 
    return 0;
}
cs


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

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

백준 1158번 조세퍼스 문제 (C++)  (0) 2019.08.24
백준 11053번 가장 긴 증가하는 부분 수열 (C++)  (0) 2019.08.24
백준 15684번: 사다리 조작 (C++)  (0) 2019.08.23
백준 16637번: 괄호 추가하기 (C++)  (0) 2019.08.21
백준 17135번: 캐슬 디펜스 (C++)  (0) 2019.08.21

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



초기 사다리의 정보를 입력받은 이후에, 사다리를 추가로 놓을 수 있는 곳들을 모두 찾아서 3개 이하로 사다리를 놓아보고, 문제에서 정해준 조건대로 i번에서 출발하면 i번 라인으로 도착할 수 있는지를 확인해주면 된다.




사다리를 모두 놓아보는 방법에는 여러가지가 있을 것 같은데, 본인은 먼저 사다리 하나를 놓을 수 있는 모든 경우를 찾아서 벡터에 담았다.



그리고 문제에서 3개 이하로만 확인하면 된다고 했기 때문에, 0개부터 3개까지 사다리를 놓아보고, i열에서 출발해서 i열로 도착할 수 있는지를 확인했다.



사다리를 놓을 수 있는 최솟값을 찾는 것이기 때문에, 중간에 어떤 경우라도 조건을 만족하면, 탐색을 멈추고 답을 출력한다.



사다리를 놓아볼 때는, 가령 (1,3) (1,4)에 놓아지는 사다리를 추가할 때는, 당연하게도 (1,4)에서 출발하는 사다리를 놓을 수 없기 때문에 이에 맞는 처리를 해주면 된다.


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
#include<iostream>
#include<vector>
using namespace std;
typedef pair<int, int> pii;
int col, m, row, map[31][11], st = 0;
bool isused[31][11], ansUpdate = false;
vector<pii> v;
int ans = -1;
 
void btk(int k, int num) {
    if (k == num) { //사다리의 개수
        
        bool suc = true; //답을 찾았는지
        for (int i = 1; i <= col; i++) {
            pii pos = { 1, i }; //출발 지점
            bool isFirst = true; //true면 가로로 이동, false면 세로로 이동
            while (pos.first <= row) {
                
                if (map[pos.first][pos.second] != 0) { //가로 사다리 만나면
                    if (isFirst == true) { //가로이동 할 차례
                        pos.second = map[pos.first][pos.second];
                        isFirst = false; //다음엔 세로 이동 하도록
                        
                    }
                    else { //세로로 이동할 차례
                        isFirst = true; //다음엔 가로로 이동하도록
                        pos.first++;
                        
                    }
                }
                else 
                    pos.first++; //가로 사다리가 없는 곳이면 아래로 이동
                
            }
            if (pos.second != i) { //출발점과 도착지점의 열값이 다르면 실패
                suc = false;
                break;
            }
        }
        if (suc) {
            ansUpdate = true;
            ans = num;
        }
        return;
    }
    if (k == 0) st = 0;
    for (int i = st; i < v.size(); i++) {
        int r = v[i].first; //r,c와 r,c+1이 사다리
        int c = v[i].second;
        if (!isused[r][c] && !isused[r][c + 1]) {
            isused[r][c] = true;
            isused[r][c + 1] = true;
            st = i;
            map[r][c] = c + 1; //r,c에서 사다리를 보면 r, c+1로 이동
            map[r][c + 1] = c; //위와 반대
            btk(k + 1, num);
            if (ansUpdate) return; //정답 찾으면 백트레킹 그만
            isused[r][c] = false;
            isused[r][c + 1] = false;
            map[r][c] = 0;
            map[r][c + 1] = 0;
        }
    }
}
int main(void) {
    cin >> col >> m >> row;
    for (int i = 0; i < m; i++) {
        int rw, st;
        cin >> rw >> st;
        map[rw][st] = st + 1;
        map[rw][st + 1] = st;
    }
 
    for (int i = 1; i <= row; i++) 
        for (int j = 1; j <= col; j++) 
            if (map[i][j] != 0)
                isused[i][j] = true; //처음부터 가로 사다리가 놓여진 곳
    
 
    //가로막대 놓을 수 있는 곳 찾아서 벡터에 시작점만 담기
    for (int i = 1; i <= row; i++) {
        for (int j = 1; j <= col - 1; j++) { //어짜피 가장 끝 열에는 사다리를 둘 수 없으니까 col -1
            if (!isused[i][j] && !isused[i][j + 1]) {
                isused[i][j] = true;
                isused[i][j + 1] = true;
                v.push_back({ i, j });
                isused[i][j] = false;
                isused[i][j + 1] = false;
            }
        }
    }
    
    
    for (int i = 0; i <= 3; i++) {
        if (ansUpdate) break; //최솟값 찾는 거니까 하나라도 찾으면 그만
        btk(0, i);
    }
    printf("%d", ans);
    return 0;
}
cs


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

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

백준 11053번 가장 긴 증가하는 부분 수열 (C++)  (0) 2019.08.24
백준 17140번: 이차원 배열과 연산 (C++)  (0) 2019.08.23
백준 16637번: 괄호 추가하기 (C++)  (0) 2019.08.21
백준 17135번: 캐슬 디펜스 (C++)  (0) 2019.08.21
백준 17406번: 배열돌리기4 (C++)  (0) 2019.08.20

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



중요한 부분은


1. 수식의 길이를 n이라고 했을 때, 넣을 수 있는 괄호의 최대 개수 찾기


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
92
93
94
95
96
97
98
99
100
#include<iostream>
#include<string>
#include<limits.h>
#include<vector>
 
using namespace std;
typedef long long ll;
int n, maxBrac, arr[20], st = 1, num[20];
vector<ll> numV; //피연산자
vector<char> oprV; //연산자
 
char opr[20];
string cmd;
bool isused[20], picked[20], done[20];
int ans = -1 * INT_MAX;
 
void init() {
    for (int i = 0; i < n; i++) {
        picked[i] = false;
        done[i] = false;
    }
}
ll cal(int a, char op, int b) { //계산 과정에서 int 범위를 벗어날 수 있다
    if (op == '+')
        return (ll)(a + b);
    else if (op == '*')
        return (ll)(a*b);
    else if (op == '-')
        return (ll)(a - b);
}
void btk(int k, int maxBr) {
    if (k == maxBr) {
        for (int i = 0; i < maxBr; i++) {
        
            picked[arr[i]-1] = true;
            picked[arr[i]] = true;
            picked[arr[i]+1] = true;
        }
        
        for (int i = 0; i < n; i++) { //괄호로 묶인 값들 계산하면서 연산자, 피연산자 벡터에 삽입
            if (!picked[i]) {
                if (num[i] != -1)
                    numV.push_back(num[i]);
                else
                    oprV.push_back(opr[i]);
            }
            else if(picked[i]){
                if (done[i]) continue;
                else {
                    numV.push_back(cal(num[i], opr[i + 1], num[i + 2]));
                    done[i] = true;
                    done[i + 1] = true;
                    done[i + 2] = true;
                }
            }
        }
 
        ll res = numV[0]; //수식 계산
        for (int i = 1; i < numV.size(); i++) {
            res = cal(res, oprV[i - 1], numV[i]);
        }
    
        if (ans < res) ans = res;
        init();
        oprV.clear();
        numV.clear();
        return;
    }
    if (k == 0) st = 1;
    for (int i = st; i < n; i += 2) {
        if (!isused[i]) {
            arr[k] = i;
            st = i;
            isused[i] = true;
            isused[i + 2] = true; //연산자를 선택하면, 바로 인접한 연산자는 고를 수 없음
            btk(k + 1, maxBr);
            isused[i + 2] = false;
            isused[i] = false;
        }
    }
}
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> cmd;
 
    maxBrac = (n + 1) / 4; //수식의 길이가 n일 때, 넣을 수 있는 괄호의 최대 개수
    for (int i = 0; i < cmd.length(); i++) {
        if (i % 2 == 0) num[i] = cmd[i]-'0'; //입력은 문자로 들어온다
        else {
            opr[i] = cmd[i];
            num[i] = -1; //입력이 음수가 들어오는 경우는 없으므로 -1로 초기화
        }
    }
    for(int i = 0 ; i <= maxBrac ; i++)
        btk(0, i);
    cout << ans;
    return 0;
}
 
cs


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

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

백준 17140번: 이차원 배열과 연산 (C++)  (0) 2019.08.23
백준 15684번: 사다리 조작 (C++)  (0) 2019.08.23
백준 17135번: 캐슬 디펜스 (C++)  (0) 2019.08.21
백준 17406번: 배열돌리기4 (C++)  (0) 2019.08.20
백준 11053번 가장 긴 증가하는 부분 수열 (C++)  (0) 2019.08.19

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


백준 16637번 괄호 추가하기라는 문제인데, 이 문제를 풀면서 했던 뻘짓을 기록해두려고 한다.


3+8*2 이런 문자열이 있다고 할 때, 결과값을 내도록 구현하려면 어떻게 해야할까?


그냥 str[0] ~ str끝까지 한 문자 한 문자 확인하려고 생각하는 순간 굉장히 피곤해진다.


324 + 232 이런 경우처럼, 한 자리수가 아닌 숫자가 존재할 수 있기 때문이다. 처음에 이렇게 접근했다가, 결과적으로 아래와 같은 뻘짓을 하게 되었다.


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
string calculate(int a, char opt, int b) {
 
    if (opt == '+') return to_string(a + b);
 
    else if (opt == '-') return to_string(a - b);
    else
        return to_string((ll)(a*b));
}
int makeAns(string cur) {
    if (cur.length() == 0) return 0;
    int res = stoi(cur.substr(0, 1));
    for (int i = 1; i < cur.length() - 1; i++) {
        if (cur[i] - '0' < INT_MAX && cur[i] - '0' > -1 * INT_MAX) continue;
        if (!(cur[i] - '0' < INT_MAX && cur[i] - '0' > -1 * INT_MAX)) {
            if (cur[i + 1] - '0' < INT_MAX && cur[i + 1] - '0' > -1 * INT_MAX) {
                res += stoi(calculate(res, cur[i], stoi(cur.substr(i + 1, 1))));
            }
            else {
                i++;
                res += stoi(calculate(res, cur[i], -1 * stoi(cur.substr(i + 2, 1))));
            }
        }
    }
    cout << "계산결과 : " << res << '\n';
}
void process() {
    string str = "";
    for (int i = 0; i < n; i++) {
        if (!picked[i]) str += cmd[i];
        else {
            if (done[i]) continue;
            else {
                int a, b;
                a = stoi(cmd.substr(i, 1));
                b = stoi(cmd.substr(i + 2, 1));
                str += calculate(a, cmd[i + 1], b);
                done[i] = true;
                done[i + 1] = true;
                done[i + 2] = true;
            }
        }
    }
    cout << str << '\n';
 
 
}
cs



위와 같은 뻘짓을 하지 않으려면, 연산자와 피연산자를 분리해서 벡터(배열)에 저장하고 있으면 된다. 연산하기가 훨씬 수월하다.


1
2
3
4
ll res = numV[0];
        for (int i = 1; i < numV.size(); i++) {
            res = cal(res, oprV[i - 1], numV[i]);
        }
cs


이렇게 간단하게 계산할 수 있다.


정상적인 수식이라면, 연산자의 개수가 피연산자의 개수보다 하나 적을 것이므로, 깔끔하게 위와 같은 반복문을 만들어낼 수 있다.



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

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

백준 2251번: 물통 (C++)  (0) 2019.08.31
백준 1525번: 퍼즐 (C++)  (0) 2019.08.30
[오답] 카카오 2018 블라인드 테스트: 무지의 먹방 라이브 C++  (0) 2019.08.20
[오답] 백준 1941 소문난 칠공주 C++  (0) 2019.08.10
[오답] 백준 1799번: 비숍 (C++)  (0) 2019.07.24

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



궁수 세 명을 최적의 위치에 배치해서, 가장 많은 적을 죽이도록 하는 문제이다.



따라서 열의 길이를 이용해서, 궁수가 위치할 수 있는 세 곳을 먼저 조합으로 뽑는다.


각각의 궁수에 대해 bfs를 돌린다. 앞에서부터 멀리있는 곳까지 확인할 것이다.


이때 중요한 것이 몇가지 있다.


궁수들은 같은 거리라면 왼쪽에 있는 적부터 공격한다. 따라서 bfs를 수행할 때, 탐색의 순서를 좌, 상, 우 이렇게 해줘야 한다.


또한 궁수들은 동시에 같은 적을 공격할 수 있다고 했기 때문에, 하나의 궁수를 가지고 탐색을 하다가 적을 발견했을 때에, 바로 그 적을 없애면 안 된다.


그걸 없애버리면 동시에 같은 적을 공격할 수 있다는 조건에 위배되기 때문이다.


set에 추가만 해주고, 이번 턴에 죽일 적을 찾았으므로, 바로 현재 궁수의 bfs를 종료해주면 된다.



세 궁수의 탐색이 사정거리만큼 모두 이루어지고 나면 set을 활용해서 지도에서 적을 지우고, set을 비워준다.



시기적절하게 초기화를 해주고, 적들을 지도에서 제거하고, 적들을 이동시키는 잔처리가 중요한 문제였다.


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
#include<iostream>
#include<queue>
#include<set>
using namespace std;
typedef pair<int, int> pii;
int m[19][18], tmp[19][18], N, M, d, st = 1, arr[19], dis[19][18];
int dr[3] = { 0,-1,0 }, dc[3] = {-1, 0, 1};
bool isused[18];
queue<pii> q;
set<pii> killed;
 
void bfs(pii start) {
    dis[start.first][start.second]++;
    q.push(start);
    while (!q.empty()) {
        pii cur = q.front(); q.pop();
        if (dis[cur.first][cur.second] >= d) continue; //사정거리 마지막 점
        for (int i = 0; i < 3; i++) {
            int nr = cur.first + dr[i];
            int nc = cur.second + dc[i];
            if (nr < 1 || nc < 1 || nr > N || nc > M || dis[nr][nc] >= 0) continue;
            if (m[nr][nc] == 1) {
                killed.insert({ nr, nc });
                return;
            }
 
            q.push({ nr, nc });
            dis[nr][nc] = dis[cur.first][cur.second] + 1;
        }
    }
}
void init() {
    for(int i = 1 ; i <= N+1 ; i++)
        for(int j = 1 ; j <= M ; j++)
            dis[i][j] = -1;
    while (!q.empty()) q.pop();
}
bool allKilled() {
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= M; j++) 
            if (m[i][j] != 0) 
                return false;
        
    return true;
}
int kill() {
    int cnt = 0;
    for (set<pii>::iterator itr = killed.begin(); itr != killed.end(); itr++) {
        m[itr->first][itr->second] = 0;
        cnt++;
    }
    killed.clear();
    return cnt;
}
void move() {
    for (int i = N; i >= 1; i--) 
        for (int j = 1; j <= M; j++) 
            m[i][j] = m[i - 1][j];
}
int ans = 0;
void btk(int k) {
    if (k == 3) {
        
        int killSum = 0;
        while (1) {
            //적 다 사라질 때까지
            if (allKilled()) break;
 
            for (int i = 0; i < 3; i++) {
                bfs({ N + 1, arr[i] });
                init();
            }
            killSum += kill();//죽은 적들 배열에서 제거
        
            move();    
        }
        if (ans < killSum) ans = killSum;
        
        for (int i = 1; i <= N; i++)
            for (int j = 1; j <= M; j++)
                m[i][j] = tmp[i][j];
        return;
    }
    if (k == 0) st = 1;
    for (int i = st; i <= M; i++) {
        if (!isused[i]) {
            arr[k] = i;
            st = i;
            isused[i] = true;
            btk(k + 1);
            isused[i] = false;
        }
    }
}
int main(void) {
    cin >> N >> M >> d;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            cin >> m[i][j];
            tmp[i][j] = m[i][j];
        }
    }
 
    btk(0);
    cout << ans;
    return 0;
}
cs


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

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

백준 15684번: 사다리 조작 (C++)  (0) 2019.08.23
백준 16637번: 괄호 추가하기 (C++)  (0) 2019.08.21
백준 17406번: 배열돌리기4 (C++)  (0) 2019.08.20
백준 11053번 가장 긴 증가하는 부분 수열 (C++)  (0) 2019.08.19
백준 1926번 그림 (C++)  (0) 2019.08.19

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



배열 돌리기 목록을 꼭 "모두 사용해야 한다"고 했다. 또한 배열을 돌리는 순서에 따라서 결과가 달라지기 때문에, 순열을 사용해서 돌릴 순서를 정해준다.


모든 경우를 다 돌려봐야 하고, 주의할 사항은, 한 순열을 돌린 이후에, 반드시 배열을 원래 상태로 초기화 시켜줘야 한다는 것이다.



배열을 돌릴 때에는, 모든 값을 보존하면서 돌리는 것이 불가능 하다. 돌리는 순서, 방향에 따라서 반드시 모서리중 어느 한 값은 손실이 발생할 수 밖에 없는데, 그 값을 정해서 미리 담아두고, 마지막에 채워주면 된다.


본인은 가장 좌측 상단의 값을 기억해두고, 그 위치를 없어지는 값으로 정했다. 마지막에 그 값이 옮겨가야 할 곳에 넣어주면 된다.



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
#include<iostream>
#include<limits.h>
struct Spin {
    int r, c, size;
}sp[8];
using namespace std;
 
int R, C, k, m[51][51],tmp[51][51], arr[8];
bool isused[8];
int Min = INT_MAX;
 
void spin(int val) {
    int rr = sp[val].r, cc = sp[val].c, size = sp[val].size;
    for (int l = 1; l <= size; l++) {
        int leftHigh = m[rr - l][cc - l]; //위쪽 변 넣을때 마지막에 넣어주기
        
        for (int row = rr - l; row <= rr + l-1; row++)  //왼쪽 변
            m[row][cc - l] = m[row+1][cc - l];
    
        for (int col = cc - l; col <= cc + l - 1; col++)  //아래쪽 변
            m[rr + l][col] = m[rr + l][col + 1];
        
 
        for (int row = rr + l; row >= rr - l + 1; row--)  //우측 
            m[row][cc + l] = m[row - 1][cc + l];
        
 
        for (int col = cc + l; col >= cc - l + 2; col--)  //상단
            m[rr - l][col] = m[rr - l][col - 1];
        
        m[rr - l][cc - l + 1] = leftHigh; //기억해 놨던 맨 왼쪽 상단 값 넣어줌
    }
    
}
 
void calMin() {
    int inMin = INT_MAX;
    for (int i = 1; i <= R; i++) {
        int Sum = 0;
        for (int j = 1; j <= C; j++) 
            Sum += m[i][j];
        
        if (inMin > Sum) inMin = Sum;
    }
    if (inMin < Min) Min = inMin;
    
}
void init() {
    for (int i = 1; i <= R; i++)
        for (int j = 1; j <= C; j++)
            m[i][j] = tmp[i][j];
}
void backTracking(int num) {
    if (num == k) {
        for (int i = 0; i < k; i++)
            spin(arr[i]);
        calMin();
        
        init(); //배열 돌리기 이전으로 초기화
        return;
    }
    for (int i = 0; i < k; i++) {
        if (!isused[i]) {
            arr[num] = i;
            isused[i] = true;
            backTracking(num + 1);
            isused[i] = false;
        }
    }
}
int main(void) {
    cin >> R >> C >> k;
    for (int i = 1; i <= R; i++) {
        for (int j = 1; j <= C; j++) {
            cin >> m[i][j];
            tmp[i][j] = m[i][j];
        }
    }
 
    for (int i = 0; i < k; i++) 
        cin >> sp[i].r >> sp[i].c >> sp[i].size;
    
    backTracking(0);
    cout << Min;
    return 0;
}
cs


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

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

백준 16637번: 괄호 추가하기 (C++)  (0) 2019.08.21
백준 17135번: 캐슬 디펜스 (C++)  (0) 2019.08.21
백준 11053번 가장 긴 증가하는 부분 수열 (C++)  (0) 2019.08.19
백준 1926번 그림 (C++)  (0) 2019.08.19
백준 10254 고속도로 C++  (0) 2019.08.17

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



정확성 테스트는, 그냥 조건대로 시뮬레이션을 돌리면 통과할 수 있지만, 효율성 테스트는 통과할 수 없다.


k의 범위가 매우 큰데, 나이브하게 풀면 k번 탐색해야하기 때문이다.



k번 탐색할 게 아니라, 최대로 음식의 개수만큼만 탐색하도록 구현할 수 있다.


음식을 먹는 데 소요되는 시간을 오름차순으로 정렬하고, 


(현 시점에서 가장 적은 시간이 소요되는 음식의 시간 * 남아있는 음식의 수)만큼의 시간을 한 번에 감소시킬 수 있다.


당연히 k도 갱신되어야 하고, 위에 계산한 시간이 k보다 작아야 가능하다.


저 시간이 k보다 크다면, 음식별 소요 시간으로 정렬해 두었던 것을, 다시 본래의 인덱스로 돌려준다. 이것 때문에 초반에 pair에 음식별 소요시간과 그 음식의 번호를 함께 저장하는 것이다.


이제는 나머지 연산을 활용해서, 먹어야할 음식을 찾아주면 된다.


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
#include <string>
#include <vector>
#include<iostream>
#include<algorithm>
 
using namespace std;
 
typedef pair<int, int> pii;
typedef long long ll;
 
bool cmp(pii a, pii b) {
    return a.second < b.second;
}
int solution(vector<int> ft, long long k) {
    vector<pii> foods;
    for (int i = 0; i < ft.size(); i++) 
        foods.push_back({ ft[i], i + 1 }); //음식의 번호는 1부터
    
    sort(foods.begin(), foods.end());
    int remain = foods.size();
    ll spend, preTime = 0; //spend = 현 시점에서 한번에 지울 수 있는 시간, pretime = 이전에 봤던 음식의 소요 시간
    for (vector<pii>::iterator itr = foods.begin(); itr != foods.end(); itr++, remain--) {
        spend = (itr->first-preTime) * remain;
        preTime = itr->first;
        if (spend == 0) continue;
        else if (spend <= k) { //한번에 spend만큼 지울 수 있으면
            k -= spend;
        }
        else { //한번에 먹을 수 있는 양보다 k가 작으면
            sort(itr, foods.end(), cmp);//다시 음식들 원위치로 정렬
            k %= remain;
            return (itr + k)->second;
        }
    }
    return -1; //먹을 수 있는 게 없어서, spend가 k보다 커진적 없이, 계속 0이라 스킵된 경우
}
int main(void) {
    vector<int> v;
    v = { 3,5,1,6,5,3 };
    int k = 20;
    solution(v, 20);
    return 0;
}
cs


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

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

카카오 2017 블라인드 테스트 1차: 다트 게임 (C++)  (0) 2019.08.25
2017 카카오 블라인드 테스트 1차: 비밀지도 (C++)  (0) 2019.08.23
카카오 2018 블라인드 테스트: 길 찾기 게임 C++  (0) 2019.08.20
카카오 2018 블라인드 테스트: 실패율 C++  (0) 2019.08.19
카카오 2018 블라인드 테스트: 오픈채팅방 C++  (0) 2019.08.19

문제 풀이 소요 시간을 획기적으로 감소시켜야 할 때 생각해 볼만한 것들



1. 정렬


2. modular 연산


3. 이분탐색



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

'알고리즘 문제 풀이 > 문제 접근 방법' 카테고리의 다른 글

다익스트라 - 함께여행  (0) 2022.11.18
메모리초과  (0) 2019.08.16
런타임 에러 발생 이유 (추가중)  (0) 2019.07.25
배열 최대/최소 기억  (0) 2019.07.09
투포인터 응용  (0) 2019.07.09

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



k번 순회하도록 해서 정확도밖에 맞추지 못한 코드이다.


순회 방법을 줄일 아이디어가 필요하다.



처음에 든 생각은, 배열에서 0이 아닌것의 개수와, 배열의 최솟값을 곱하면 이만큼을 한 번에 먹는 것으로 처리할 수 있다는 것.


다른 생각은 정렬해서 k보다 작을동안 묶어서 빼준 이후에, 한 번에 먹을 수 있는 게 k보다 커지면 다시 순회하는 방법이 있을 것 같다.


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
#include <string>
#include <vector>
#include<iostream>
typedef long long ll;
using namespace std;
 
int len;
 
 
int solution(vector<int> ft, long long k) {
    bool done = false;
    int answer = 0;
    len = ft.size();
    ll j = 0;
    //findNext(&ft, j);
 
    int cnt = 0, Min = 1000000000;
    for (int i = 0; i < ft.size(); i++) {
        if (ft[i] != 0) cnt++;
        if (ft[i] < Min) Min = ft[i];
    }
 
    for (ll i = 1; i <= k; i++) {
        if (ft[j] != 0) {
            ft[j] -= 1;
        }
        for (int k = 0; k < len; k++) {
            j++;
            if (j == len) j = 0;
            if (ft[j] == 0) {
                if(k == len - 1) done = true; //모든 원소가 0
                continue;
            }
            else
                break;
            
        }
        //for (int k = 0; k < ft.size(); k++) {
        //    cout << ft[k] << ' ';
        //}
        //cout << '\n';
    }
    //cout << "답 : " << j + 1 << '\n';
    //if (done) cout << -1;
    //else
    //     cout << j + 1;
    if (done) return -1;
    else
        return j + 1;
}
int main(void) {
    vector<int> food{ 1,2,2,5 };
    int k = 13;
    solution(food, k);
    return 0;
}
cs


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

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

백준 1525번: 퍼즐 (C++)  (0) 2019.08.30
연산자 우선 순위가 없는 경우 +, -, * 연산 구현  (0) 2019.08.21
[오답] 백준 1941 소문난 칠공주 C++  (0) 2019.08.10
[오답] 백준 1799번: 비숍 (C++)  (0) 2019.07.24
백준 1759번: 암호 만들기 (C++)  (0) 2019.07.23

+ Recent posts

티스토리툴바