알고리즘 문제/BOJ

16931번 겉넓이 구하기

parkit 2019. 3. 21. 15:27
728x90
반응형

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



쉬운 문제인줄 알았는데, 계속 제출해봐도 틀렸다고 떴다.


맞은 사람들의 코드 길이를 보니 무척 짧았다. 



결국 생각해보니 해결 방법은 


높이(height)를 갱신하면서, 높이 차이(Map[행][열] - height)를 이용한다.




틀린 코드 : 노가다식 하드 코드

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
#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
#include <set>
#include <tuple>
 
#pragma warning(disable:4996)  
#pragma comment(linker, "/STACK:336777216")
 
using namespace std;
 
int N = 0, M = 0;
 
int Map[102][102] = { 0, };
 
int surface()
{
    int ret = 0;
 
    ret += N*M;
 
    for (int i = 0; i < N; i++)
    {
        int Max = -1;
 
        for (int j = 0; j < M; j++)
        {
            if (Max < Map[i][j]) Max = Map[i][j];
        }
 
        ret += Max;
    }
 
    for (int j = 0; j < M; j++)
    {
        int Max = -1;
 
        for (int i = 0; i < N; i++)
        {
            if (Max < Map[i][j]) Max = Map[i][j];
        }
 
        ret += Max;
    }
 
    return 2*ret;
}
 
int inside()
{
    int ret = 0;
 
    // 행
    for (int i = 1; i < N - 1; i++)
    {
        for (int j = 0; j < M; j++)
        {
            if (Map[i - 1][j] <= Map[i][j] && Map[i][j] <= Map[i + 1][j]) continue;        
            else if (Map[i - 1][j] >= Map[i][j] && Map[i][j] >= Map[i + 1][j]) continue;
            else if (Map[i - 1][j] <= Map[i][j] && Map[i][j] >= Map[i + 1][j]) continue;
            else ret += abs(Map[i - 1][j] - Map[i][j]) + abs(Map[i][j] - Map[i + 1][j]);        
        }        
    }
 
    // 열
    for (int j = 1; j < M - 1; j++)
    {
        for (int i = 0; i < N; i++)
        {
            if (Map[i][j - 1] <= Map[i][j] && Map[i][j] <= Map[i][j + 1]) continue;
            else if (Map[i][j - 1] >= Map[i][j] && Map[i][j] >= Map[i][j + 1]) continue;
            else if (Map[i][j - 1] <= Map[i][j] && Map[i][j] >= Map[i][j + 1])continue;
            else ret += abs(Map[i][j - 1] - Map[i][j]) + abs(Map[i][j] - Map[i][j + 1]);
        }
    }
 
    return ret;
}
 
int main(void)
{
    scanf("%d %d", &N, &M);
 
    for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) scanf("%d", &Map[i][j]);
 
    printf("%d\n", surface() + inside());
 
    return 0;
}
cs







정답 코드

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
#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
#include <set>
#include <tuple>
 
#pragma warning(disable:4996)  
#pragma comment(linker, "/STACK:336777216")
 
using namespace std;
 
int N = 0, M = 0;
 
int Map[102][102] = { 0, };
 
int main(void)
{
    int ans = 0, sum = 0;
 
    scanf("%d %d", &N, &M);
 
    for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) scanf("%d", &Map[i][j]);
 
    ans += 2 * N * M;
 
    for (int i = 0; i < N; i++)
    {
        int height = Map[i][0];
 
        sum += Map[i][0];
 
        for (int j = 1; j < M; j++)
        {
            if (height < Map[i][j]) sum += Map[i][j] - height;        
            
            height = Map[i][j];
        }
    }
 
    ans += 2*sum;
 
    sum = 0;
 
    for (int j = 0; j < M; j++)
    {
        int height = Map[0][j];
 
        sum += Map[0][j];
 
        for (int i = 1; i < N; i++)
        {
            if (height < Map[i][j]) sum += Map[i][j] - height;
                    
            height = Map[i][j];
        }
    }
 
    ans += 2 * sum;
 
    printf("%d\n", ans);
 
    return 0;
}
cs



















728x90
반응형
저작자표시 (새창열림)