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



2차원 배열을 문자열로 맵핑해서 해결한다.



1 2 3

4 5 6

7 8 0 


위와 같은 2차원 배열이라면 "123456780" 이러한 문자열이 되는 것이다.


0의 인덱스로부터 2차원 배열에서 0의 위치를 알아낼 수 있다.



한번의 시행에서, 빈칸의 위치를 옮길 수 있는 위치를 찾아준 다음에, 이전 시행에서 찾은 경우만큼만 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
#include<iostream>
#include<set>
#include<string>
#include<queue>
#include<algorithm>
using namespace std;
 
const int dzero[4] = { -3, 3, -1, 1 }; //상하좌우
const int dr[4] = { -1,1,0,0 };
const int dc[4] = { 0,0,-1, 1 };
 
int main(void) {
    string str ="", dst = "123456780";
    
    for (int i = 0; i < 9; i++) {
        int input;
        cin >> input;
        str += input + '0';
    }
    
    set<string> vis;
    vis.insert(str);
    
    queue<string> q;
    q.push(str);
    int cnt = 0;
    
    while(!q.empty()) {
        int qSize = q.size(); //이전 시행에 찾았던 0이 이동 가능한 경우만 실행
        for (int i = 0; i <qSize; i++) {
            string cur = q.front(); //현재 문자열
            q.pop();
 
            if (cur == dst) { //목적 문자랑 같으면 종료
                cout << cnt;
                return 0;
            }
            //cnt++;
 
            int zeroPos=0; //0위치 검색
            for (int j = 0; j < cur.length(); j++) {
                if (cur[j] == '0') {
                    zeroPos = j;
                    break;
                }    
            }
            
            //문자열의 0의 위치로부터 2차원 배열에서의 위치를 맵핑
            int zeroR = zeroPos / 3;
            int zeroC = zeroPos % 3;
 
            for (int j = 0; j < 4; j++) { //0이 움직일 수 있는 방향을 찾음
                int nr = zeroR + dr[j];
                int nc = zeroC + dc[j];
                if (nr < 0 || nc < 0 || nr >= 3 || nc >= 3) continue;
                
                string next = cur;
                swap(next[zeroPos], next[zeroPos + dzero[j]]);
 
                if (vis.find(next) == vis.end()){
                    vis.insert(next);
                    q.push(next);
                }
            }
        }
        cnt++; //이전에 찾은 경우들 다 해보고 
    }
    cout << -1;
    return 0;
}
 
cs



참고: http://blog.naver.com/PostView.nhn?blogId=kks227&logNo=220438835865

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

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

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

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



문제를 잘못 이해해서 시간을 많이 낭비한 문제이다.


레지스터에 저장될 수 있는 수인 n은, 10000 미만, 0 이상의 수가 맞기는 한데, 무조건 네 자리로 이루어져 있다.


즉 123 이라고 하더라도, 그냥 123이 아니라 _123이라는 것이다. 123에 L연산을 하면 231이 되지만, _123에 L연산을 해봐야


123_ 이고, 결국 123이다.



본인처럼 잘못 이해하고 풀게 되면 시간초과에 걸리게 된다. 틀렸습니다가 아니라 시간 초과라서, 로직이 잘못되었다는 걸 아는데까지 시간이 오래 걸렸다.



마지막에, 최적의 결과를 내기 위한 연산의 흐름을 출력해야 하기 때문에, 큐에 삽입될 때마다 이전 노드와 사용된 연산을 parent 배열에 저장해준다.


parent[다음 수] = {이전 수, 사용된 연산} 이렇게 된다.


마지막에는 결국 parent[목표 수] 부터 시작해서 거꾸로 타고 올라가면서 처음 수가 나올 때까지 사용된 연산을 거꾸로 출력해주면 된다.



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
#pragma warning(disable :4996)
#include<iostream>
#include<queue>
#include<string>
#include<vector>
using namespace std;
 
int T, src, dst;
char cmd[4] = { 'D', 'S', 'L','R' };
pair<int, char> parent[10000];
 
bool vis[10000];//초기화 필요
queue<int> q;
void bfs() {
    vis[src] = true;
    q.push(src);
 
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        //cout << cur << '\n';
        if (cur == dst) return;
 
        for (int i = 0; i < 4; i++) {
            int next;
            if (cmd[i] == 'D') {
                next = 2 * cur;
                if (next > 9999) next %= 10000;
            }
            else if (cmd[i] == 'S') {
                next = cur - 1;
                if (cur == 0) next = 9999;
            }
            else if (cmd[i] == 'L') 
                next = (cur % 1000) * 10 + cur / 1000;
            
            else if (cmd[i] == 'R') 
                next = (cur % 10) * 1000 + cur / 10;
            
            if (vis[next] || next > 10000) continue;
            q.push(next);
            vis[next] = true;
            parent[next] = { cur, cmd[i] }; //next로 숫자가 변할 때 사용된 명령
        }
    }
}
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> T;
    while (T--) {
        cin >> src >> dst;
        bfs();
 
        pair<int, char> prev;
        prev = parent[dst];
        vector<char> v;
        v.push_back(prev.second);
 
        while (1) {
            //cout << prev.first << '\n';
            if (prev.first == src) break;
            prev = parent[prev.first];
            v.push_back(prev.second);
        }
        for (int i = v.size() - 1; i >= 0; i--)
            cout << v[i];
        cout << '\n';
 
        v.clear();
        for (int i = 0; i < 10000; i++)
            vis[i] = false;
        while (!q.empty()) q.pop();
    }
 
    return 0;
}
 
cs


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

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

백준 1987번: 알파벳 (c++)  (0) 2019.09.01
백준 12851번: 숨바꼭질2 (C++)  (0) 2019.08.31
백준 13913번: 숨바꼭질 4 (C++)  (0) 2019.08.30
백준 3190번: 뱀 (C++)  (0) 2019.08.30
백준 1339번: 단어 수학 (C++)  (0) 2019.08.29

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



숨바꼭질 시리즈의 네 번째 문제이다. 이 문제는 최단 시간을 구해주고, 동시에 경로를 같이 출력해주면 된다.


경로를 출력하는 방법에는 여러가지가 있을 수 있겠지만, 현재 노드를 다음 노드의 부모라고 보고 parent 배열에 저장해주었다.



다만 이렇게 할 경우, 시작점과 목적지가 같은 경우에 올바른 경로를 출력할 수 없기 때문에 따로 예외 처리를 해주어야 한다.



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
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
int src, dst, m[100002], dr[3] = { 0,1,2 }, dis[100002]; //-1, +1, *2
bool vis[100002];
vector<int> path;
queue<int> q;
int parent[100002];
void bfs() {
    
    q.push(src);
    dis[src]++;
    
    path.push_back(src);
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
 
        for (int i = 0; i < 3; i++) {
            int np;
            if (dr[i] == 0) np = cur - 1;
            else if (dr[i] == 1) np = cur + 1;
            else
                np = cur * 2;
 
            if (np < 0 || np > 100000 || dis[np] >= 0) continue;
            
            path.push_back(np);
            
            parent[np] = cur; //현재 노드를 다음 노드의 부모로 저장
            q.push(np);
            dis[np] = dis[cur] + 1;
 
        }
    }
}
 
int main(void) {
 
    cin >> src >> dst;
    for (int i = 0; i <= 100000; i++)
        dis[i] = -1;
    bfs();
    cout << dis[dst] << '\n';
    if (src == dst) cout << src; //출발지와 목적지가 같은 경우 예외 처리
    else {
        int prev = parent[dst];
        vector<int> v;
        v.push_back(dst);
        v.push_back(prev);
        while (1) {
            if (prev == src) break; //출발지가 나올 때까지 타고 올라감
            prev = parent[prev];
            v.push_back(prev);
        }
        for (int i = v.size() - 1; i >= 0; i--)
            cout << v[i] << ' ';
    }
 
    return 0;
}
cs


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

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

백준 12851번: 숨바꼭질2 (C++)  (0) 2019.08.31
백준 9019번: DSLR (C++)  (0) 2019.08.30
백준 3190번: 뱀 (C++)  (0) 2019.08.30
백준 1339번: 단어 수학 (C++)  (0) 2019.08.29
백준 1644번: 소수의 연속합 (C++)  (0) 2019.08.29

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



문제에 적힌 절차 그대로 구현해주면 된다.


중요한 포인트는, 매회 이동을 할 때, 몸길이를 늘려서 다음 칸을 확인한다는 것이다.


늘린 이후에, 사과라면 몸길이 유지, 사과가 아니라면 몸길이 감소 순서이다.



게임 시작 시간으로부터 X초가 끝난 뒤에라고 문제에서 명시된 것처럼, 초가 끝난 이후에, 방향을 바꿔준다.


가령 3초에 뱀이 회전해야 한다면, 2~3초의 이동이 끝난 이후에 방향을 바꿔주면 된다.



머리의 이동은 어렵지 않게 구현할 수 있다. 꼬리의 다음 위치를 파악하는 것이 중요한데, 머리의 회전과 꼬리의 회전이 동시에 일어나지 않기 때문에, 꼬리를 이동할 때 마다, 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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include<iostream>
#include<vector>
#include<queue>
 
using namespace std;
typedef pair<int, int> pii;
int n, m[101][101], k, L, age[101][101];
 
int dr[4] = { 0,1,0,-1 };
int dc[4] = { 1,0,-1,0 };
struct Snake {
    pii head;
    pii tail;
    int dir;
};
queue<Snake> q;
 
int time = 0;
vector<pair<int, char > > turn;
 
void bfs(Snake s) {
    q.push(s);
    m[1][1] = 1;
    int ag = 0;
    age[1][1] = 1;
 
    while (!q.empty()) {
 
        Snake cur = q.front();
        q.pop();
 
        time++;
 
        int nr = cur.head.first + dr[cur.dir];
        int nc = cur.head.second + dc[cur.dir];
        if (nr <= 0 || nc <= 0 || nr > n || nc > n || m[nr][nc] == 1)
            return; //충돌 검사
 
        if (m[nr][nc] == 4) { //머리 늘려서 이동했는데 사과인 경우
            m[nr][nc] = 1;
            age[nr][nc] = 1; //나중에 꼬리 갱신할 때, 가장 오래된 몸통을 꼬리로 하기 위함
        }
        else {
            m[nr][nc] = 1;
            age[nr][nc] = 1;
            //사과 아니면 꼬리 이동
 
            pii pos;
            int maxAge = 0;
            for (int j = 0; j < 4; j++) {
 
                int tnr = cur.tail.first + dr[j];
                int tnc = cur.tail.second + dc[j];
                if (tnr <= 0 || tnc <= 0 || tnr > n || tnc > n || age[tnr][tnc] == 0) continue;
 
                if (age[tnr][tnc] > maxAge) {
                    maxAge = age[tnr][tnc];
                    pos = { tnr, tnc }; //가장 오래된 몸통
                }
            }
            m[cur.tail.first][cur.tail.second] = 0; //꼬리 제거
            age[cur.tail.first][cur.tail.second] = 0;
            cur.tail.first = pos.first; //새로운 꼬리
            cur.tail.second = pos.second;
            m[nr][nc] = 1; //다음 머리의 위치가 직전 꼬리의 위치였을 경우
            age[nr][nc] = 1;
        }
        cur.head.first = nr;
        cur.head.second = nc;
 
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                if (age[i][j] > 0) age[i][j]++; //전체 몸통 나이 증가
 
 
        //초 끝나고 방향 전환
        for (int i = 0; i < turn.size(); i++) {
 
            if (turn[i].first == time) {
                if (turn[i].second == 'L') {
                    cur.dir = (cur.dir + 3) % 4;
                    break;
                }//왼쪽으로 90도
                else {
                    cur.dir = (cur.dir + 1) % 4;
                    break;
                }//오른쪽 90
            }
        }
        q.push(cur);
 
    }
}
int main(void) {
    cin >> n >> k;
    for (int i = 0; i < k; i++) {
        int r, c;
        cin >> r >> c;
        m[r][c] = 4; //사과
    }
 
    cin >> L;
    for (int i = 0; i < L; i++) {
        int sec;
        char d;
        cin >> sec >> d;
        turn.push_back({ sec, d });
    }
 
    Snake snake;
    snake.head = { 1, 1 };
    snake.tail = { 1, 1 };
 
    snake.dir = 0;
    bfs(snake);
    cout << time;
    return 0;
}
cs


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

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

백준 9019번: DSLR (C++)  (0) 2019.08.30
백준 13913번: 숨바꼭질 4 (C++)  (0) 2019.08.30
백준 1339번: 단어 수학 (C++)  (0) 2019.08.29
백준 1644번: 소수의 연속합 (C++)  (0) 2019.08.29
백준 2003번: 수들의 합 2 (C++)  (0) 2019.08.29

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



순열로 풀게 되면 시간 초과가 날 것이고, 다른 방법이 필요하다.



ABC 이런 문자열이 있으면, C에는 1의 가중치를, B에는 10의 가중치를, A에는 100의 가중치를 준다. 


마찬가지로 또 다른 문자열 AR이 있다고 하면, A에는 10의 가중치를, R에는 1의 가중치를 준다.


그렇다면 전체 가중치는 A에 110, B에 10, C에 1 R에 1일 것이다. 이를 가중치 내림차순으로 사용된 알파벳만 골라서


110 * 9 + 10 * 8 + 1 * 7 + 1 * 6 이렇게 계산해주면 된다. 


즉 높은 가중치에서부터 9부터 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
#pragma warning(disable :4996)
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
 
int cnt[26], n;
 
bool cmp(int a, int b) {
    return a > b;
}
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n;
 
    vector<string> wrd;
    for (int i = 0; i < n; i++) {
        string tmp;
        cin >> tmp;
        wrd.push_back(tmp);
    }
 
    
    for (int i = 0; i < wrd.size(); i++) {
        int val = 1; //가중치
        for (int j = wrd[i].length()-1; j >= 0; j--) { //문자열 우측부터 읽음
            cnt[wrd[i][j] - 'A'] += val; 
            val *= 10; // 좌측(자리수가 커지는 방향) 갈 때마다  
        }
    }
    
    vector<int> usedAlpha; 
    for (int i = 0; i < 26; i++) 
        if (cnt[i] > 0) //사용된 문자
            usedAlpha.push_back(cnt[i]);//사용된 문자만 벡터에 담음
    
    sort(usedAlpha.begin(), usedAlpha.end(), cmp); //가중치 내림차순으로 정렬
    
    ll ans = 0; int num = 9;
    for (int i = 0; i < usedAlpha.size(); i++)
        ans += usedAlpha[i] * num--; //가중치 큰 알파벳부터 9씩 곱해서 더해주면 됨
 
    cout << ans;
 
    return 0;
}
 
cs



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

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

백준 13913번: 숨바꼭질 4 (C++)  (0) 2019.08.30
백준 3190번: 뱀 (C++)  (0) 2019.08.30
백준 1644번: 소수의 연속합 (C++)  (0) 2019.08.29
백준 2003번: 수들의 합 2 (C++)  (0) 2019.08.29
백준 13458번: 시험 감독 (C++)  (0) 2019.08.29

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


n이하의 소수를 모두 구해놓고 투포인터를 적용해주면 된다.


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<vector>
using namespace std;
int n, prime[4000000], num = 1;
 
void findPrime() {
    prime[0] = 2;
    
    for (int i = 3; i <= n; i++) {
        bool isPrime = true;
        for (int j = 2; j*j <= i; j++) {
            if (i % j == 0) {
                isPrime = false;
                break;
            }    
        }
        if (isPrime) prime[num++] = i;
    }
}
int main(void) {
    cin >> n;
    findPrime();
    
    int cnt = 0, low = 0, high = 0;
    long long Sum = prime[0];
    while (1) {
        if (high >= num) break;
        
        if (Sum < n) {
            Sum += prime[++high];
        }
        else if (Sum == n) {
            cnt++;
            Sum += prime[++high];
        }
        else {
            Sum -= prime[low++];
            if (low > high) {
                if (prime[high] >= n) break;
                else {
                    high = low;
                    Sum = prime[high];
                }
            }
        }
    }
    cout << cnt;
}
cs


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

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

백준 3190번: 뱀 (C++)  (0) 2019.08.30
백준 1339번: 단어 수학 (C++)  (0) 2019.08.29
백준 2003번: 수들의 합 2 (C++)  (0) 2019.08.29
백준 13458번: 시험 감독 (C++)  (0) 2019.08.29
백준 14500번: 테트로미노 (C++)  (0) 2019.08.29

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



n이 10000 이하이고, 시간 제한이 0.5초이기 때문에, n^2 풀이로 풀게 되면 시간 초과가 날 것이다.


따라서 O(n)에 해결할 수 있도록 투포인터를 사용하도록 한다.



초기에 st와 en을 모두 시작점으로 정해두고, en이 범위 밖으로 벗어날 때까지 진행해준다.



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
#include<iostream>
 
using namespace std;
int n, m, arr[10001];
int main(void) {
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        cin >> arr[i];
 
    int st = 0, en = 0, cnt = 0;
    long long Sum = arr[0];
 
    while (1) {
        //합이 부족해서 en이 우측으로 움직이는 건데, en이 밖으로 나갔다는 것은 더 볼 필요가 없다는 것
        //st가 우측으로 움직여봤자 합은 더 감소하기 때문에
        if (en >= n) break; 
        
        if (Sum == m) {
            Sum += arr[++en]; //딱 만족할 때 en 증가
            cnt++;
        }
 
        else if (Sum < m) Sum += arr[++en];
 
        else {
            
            Sum -= arr[st++];
            if (st > en) {
                en = st;
                Sum = arr[en];
            }
        }
    }
    cout << cnt;
    return 0;
}
cs


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

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

백준 1339번: 단어 수학 (C++)  (0) 2019.08.29
백준 1644번: 소수의 연속합 (C++)  (0) 2019.08.29
백준 13458번: 시험 감독 (C++)  (0) 2019.08.29
백준 14500번: 테트로미노 (C++)  (0) 2019.08.29
백준 14503번: 로봇 청소기 (C++)  (0) 2019.08.28

An array A consisting of N integers is given. A triplet (P, Q, R) is triangular if 0 ≤ P < Q < R < N and:

  • A[P] + A[Q] > A[R],
  • A[Q] + A[R] > A[P],
  • A[R] + A[P] > A[Q].

For example, consider array A such that:

A[0] = 10 A[1] = 2 A[2] = 5 A[3] = 1 A[4] = 8 A[5] = 20

Triplet (0, 2, 4) is triangular.

Write a function:

int solution(vector<int> &A);

that, given an array A consisting of N integers, returns 1 if there exists a triangular triplet for this array and returns 0 otherwise.

For example, given array A such that:

A[0] = 10 A[1] = 2 A[2] = 5 A[3] = 1 A[4] = 8 A[5] = 20

the function should return 1, as explained above. Given array A such that:

A[0] = 10 A[1] = 50 A[2] = 5 A[3] = 1

the function should return 0.

Write an efficient algorithm for the following assumptions:

  • N is an integer within the range [0..100,000];
  • each element of array A is an integer within the range [−2,147,483,648..2,147,483,647]


문제는 위와 같다.


조건은 저렇게 위에 세 개의 부등식으로 나와있지만, 정렬을해서 확인하면 작은 두 원소의 합이 가장 큰 원소보다 크면 성립하게 된다.


오버플로우 방지를 위해 하나의 항을 이항해서 계산해주면 된다.


1
2
3
4
5
6
7
8
9
10
11
12
#include <algorithm>
int solution(vector<int> &A) {
    // write your code in C++14 (g++ 6.2.0)
    if(A.size() < 3) return 0;
    sort(A.begin(), A.end());
    for(int i = 0 ; i <= A.size()-3 ; i++){
        if(A[i] > A[i+2]-A[i+1]) //오버플로우 방지
            return 1;
    }
    return 0;
}
 
cs


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

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



총감독관은 무조건 1명은 존재해야 하기 때문에 기본적으로 답은 n부터 시작한다.


시험장마다의 인원보다 b가 크다면, 총감독관 혼자 커버할 수 있기 때문에 시험장 인원을 0으로 갱신해준다.


그렇지 않다면 시험장 인원에서 총감독관이 감시하고 있는 인원의 수인 b를 감소시켜준다.



다음으로 필요한 부감독관의 수를 계산한다. 1명이라도 부감독관이 감시할 수 있는 사람보다 수가 많으면 부감독관 한 명이 더 필요하기 때문에, 갱신한 시험장 인원을 c로 나눈 나머지가 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
#include<iostream>
#include<algorithm>
using namespace std;
int n, arr[1000001], b, c;
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n;
    for (int i = 0; i < n; i++) 
        cin >> arr[i];
    cin >> b >> c;
 
    for (int i = 0; i < n; i++) {
        if (arr[i] <= b) arr[i] = 0;
        else arr[i] -= b;
    }
    
    long long ans = n;
    
    for (int i = 0; i < n; i++) {
        if (arr[i] % c != 0) ans = ans + (arr[i] / c) + 1;
        else
            ans = ans +  (arr[i] / c);
    }
    cout << ans;
    return 0;
}
cs


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

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

백준 1644번: 소수의 연속합 (C++)  (0) 2019.08.29
백준 2003번: 수들의 합 2 (C++)  (0) 2019.08.29
백준 14500번: 테트로미노 (C++)  (0) 2019.08.29
백준 14503번: 로봇 청소기 (C++)  (0) 2019.08.28
백준 14888번: 연산자 끼워넣기 (C++)  (0) 2019.08.27

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


이차원 배열로 주어지는 격자에서, 모든 테트로미노 모양을 다 넣어보면 된다.


주어지는 다섯개의 테트로미노를 회전 또는 대칭해서 얻을 수 있는 모양들까지 포함해서 계산해주면 된다.


가능한 모양은 총 19개이다.


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>
#include<vector>
using namespace std;
int row, col, m[501][501];
int Max = -1;
 
//가능한 모양은 총 19개이다
vector<int> vr[19] = { { 1,2,3 },{ 0,0,0 },{ 0,1,1 },{ 1,2,2 },{ 0,0,-1 },{ 0,1,2 },{ -1,-1,-1 },{ 0,0,1 },{ -1,0,1 },{ -1,0,0 },{ 1,1,2 },{ 1,1,2 },
{ 0,-1,-1 },{ -1,-1,-2 },{ 0,1,1 },{ 0,-1,-2 },{ 1,1,1 },{ -1,-2,-2 },{ 0,0,1 } };
 
vector<int> vc[19] = { { 0,0,0 },{ 1,2,3 },{ 1,0,1 },{ 0,0,1 },{ 1,2,2 },{ 1,1,1 },{ 0,1,2 },{ 1, 2, 1 },
{ 1,1,1 },{ 1,1,2 },{ 0,1,0 },{ 0,1,1 },{ 1,1,2 },{ 0,1,1 },{ 1,1,2 },{ 1,1,1 } ,{ 0,1,2 } ,{ 0,0,1 } ,{ 1,2,2 } };
 
void calculate() {
    int cnt = 0;
    for (int con = 0; con < 19; con++) {
 
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                int Sum = m[i][j];
                bool isBreak = false;
 
                for (int k = 0; k < 3; k++) {
                    int nr = i + vr[con][k];
                    int nc = j + vc[con][k];
                    if (nr < 0 || nc < 0 || nr >= row || nc >= col) {
                        isBreak = true;
                        break;
                    }
                    Sum += m[nr][nc];
 
                }
                if (!isBreak)
                    if (Sum > Max) Max = Sum;
            }
        }
    }
 
}
int main(void) {
    cin >> row >> col;
    for (int i = 0; i < row; i++)
        for (int j = 0; j < col; j++)
            cin >> m[i][j];
 
    calculate();
    cout << Max << '\n';
    return 0;
}
cs


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

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

백준 2003번: 수들의 합 2 (C++)  (0) 2019.08.29
백준 13458번: 시험 감독 (C++)  (0) 2019.08.29
백준 14503번: 로봇 청소기 (C++)  (0) 2019.08.28
백준 14888번: 연산자 끼워넣기 (C++)  (0) 2019.08.27
백준 11328번 Strfry (C++)  (0) 2019.08.25

+ Recent posts

티스토리툴바