16931번 겉넓이 구하기

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

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

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

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

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

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

#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;
}

정답 코드

#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;
}