BOJ 2140 지뢰찾기

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

단순하게 구현하면 되는 문제입니다.

맵의 크기가 n이라고 가정했을 때,

테두리 옆의 # 즉 숫자 옆의 #들만 신경쓰면 됩니다.

그 외의 #들은 지뢰가 있을 수도 있고 없을 수도 있지만, 저희는 다 있다고 가정하고 풀어야합니다.

문제에서 요구하는 것이 최댓값이기 때문입니다.

테두리 옆의 #들은 8방향으로 검사를 해서 만약 주변의 숫자 중에 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
#include <iostream>
#include <queue>
 
using namespace std;
 
char map[100][105];
int dx[8] = { 1, 0, -1, 0, -1, 1, 1, -1 };
int dy[8] = { 0, 1, 0, -1, 1, 1, -1, -1 };
int n;
 
bool check(int x, int y) {
    for (int i = 0; i < 8; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
 
        if (nx < 0 || ny < 0 || nx >= n || ny >= n) {
            continue;
        }
 
        if (map[nx][ny] == '0') return 0;
    }
 
    return 1;
}
 
void doMinus(int x, int y) {
    for (int i = 0; i < 8; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
 
        if (nx < 0 || ny < 0 || nx >= n || ny >= n) {
            continue;
        }
 
        if (map[nx][ny] >= '0' && map[nx][ny] <= '9') map[nx][ny]--;
    }
}
 
int main() {
    cin >> n;
 
    if (n <= 2) {
        cout << 0;
        return 0;
    }
 
    int ret = (n - 2) * (n - 2);
 
    for (int i = 0; i < n; i++) cin >> map[i];
 
    for (int i = 1; i < n - 1; i++) {
        for (int j = 1; j < n - 1; j++) {
            if (i == 1 || j == 1 || i == n - 2 || j == n - 2) {
                if (check(i, j)) {
                    doMinus(i, j);
                }
                else {
                    ret--;
                }
            }
        }
    }
 
    cout << ret;
 
    return 0;
}
cs


저작자표시

'알고리즘 > 구현' 카테고리의 다른 글

[3190] 뱀  (4) 2018.01.10
[12845] 모두의 마블  (0) 2017.08.26
[12841] 정보대 등산  (0) 2017.08.23
[1700] 멀티탭 스케줄링  (0) 2017.08.01
[1992] 쿼드 트리  (0) 2017.07.30

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


간단한 문제입니다.

레벨이 변하지 않으므로, 최대값의 레벨을 가진 카드의 양방향으로 더해나가면 해결되는 문제입니다.


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
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <string.h>
#include <cmath>
#define ll long long
#define mp make_pair
#define pii pair<int, int>
#define vi vector<int>
#define vii vector<pair<int, int> >
#define vll vector<ll>
 
#define MOD 86400
#define INF 0x7fffffff
#define MAX_SIZE (int)1e5
 
using namespace std;
//ios::sync_with_stdio(false); cin.tie(0);
int n;
int arr[(int)1e3];
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> n;
 
    int M = 0;
    int pos;
 
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
 
        if (arr[i] > M) {
            M = arr[i];
            pos = i;
        }
    }
 
    int ret = 0;
 
    for (int i = pos - 1; i >= 0; i--) {
        ret += M + arr[i];
    }
 
    for (int i = pos + 1; i < n; i++) {
        ret += M + arr[i];
    }
 
    cout << ret;
 
    return 0;
}
cs


저작자표시

'알고리즘 > 구현' 카테고리의 다른 글

[3190] 뱀  (4) 2018.01.10
[2140] 지뢰찾기  (0) 2017.12.27
[12841] 정보대 등산  (0) 2017.08.23
[1700] 멀티탭 스케줄링  (0) 2017.08.01
[1992] 쿼드 트리  (0) 2017.07.30

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


단순 구현? 일 것 같습니다.


횡단보도를 한 번만 할 수 있다?


즉. 왼쪽길로 쭉 가다가 횡단보도 한번 건너서 오른쪽 길로 쭉 갈 수 밖에 없습니다.

여기서 두가지 예외는 왼쪽 길로 아예 안가고 횡단 보도를 바로 건너서 오른쪽 길로 쭉 가는 방법과

왼쪽 길로 쭉 가서 횡단 보도를 건너서 정보대에 도착하는 방법이 있는데

사실 예외라고 하기엔.. 예외처리를 안해줘도 되기 때문에....ㅎㅎ...



그림으로 표현하면 이렇습니다!

빨간색길과 검은색길 초록색 길!


다 같은 말이죠


그렇다면 i번째에서 횡단보도를 건너는 거리의 식은


거리i = i번째 까지의 왼쪽 길 연속 합 + 횡단 보도 i의 거리 + 1부터 정보대까지의 오른쪽 거리 - 1부터 i까지의 거리


입니다.!


코드는 아래와 같습니다.


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
#include <iostream>
#include <string>
#include <vector>
#include <queue>
 
#define ll long long
#define mp make_pair
#define pii pair<int, int>
#define vi vector<int>
#define vii vector<pair<int, int> >
#define vll vector<ll>
 
#define MOD 86400
#define INF 0x7fffffff
#define MAX_SIZE (int)1e5
 
using namespace std;
//ios::sync_with_stdio(false); cin.tie(0);
 
int cross[MAX_SIZE + 1];
ll edge[MAX_SIZE + 1][2];
 
int main() {
    ios::sync_with_stdio(false);
 
    int n;
    cin >> n;
 
    for (int i = 1; i <= n; i++) cin >> cross[i];
 
    for (int i = 0; i < 2; i++) {
        for (int j = 2; j <= n; j++) {
            cin >> edge[j][i];
            edge[j][i] += edge[j - 1][i];
        }
    }
 
    ll ret = 1e16;
    int idx = 0;
 
    for (int i = 1; i <= n; i++) {
        ll tmp = edge[i][0] + cross[i] + edge[n][1] - edge[i][1];
 
        if (tmp < ret) {
            ret = tmp;
            idx = i;
        }
    }
 
    cout << idx << ' ' << ret;
 
    return 0;
}
 
cs


저작자표시

'알고리즘 > 구현' 카테고리의 다른 글

[2140] 지뢰찾기  (0) 2017.12.27
[12845] 모두의 마블  (0) 2017.08.26
[1700] 멀티탭 스케줄링  (0) 2017.08.01
[1992] 쿼드 트리  (0) 2017.07.30
[14488] 준오는 급식충이야!  (0) 2017.07.29

+ Recent posts

티스토리툴바