[BOJ] [구현]16931번 겉넓이 구하기

 

2차원 배열로 받아서, 

가로, 세로로 순서대로 읽어나가면서 앞칸이 자기보다 낮으면, 그 차이만큼 답을 더해주면 된다.

 

근데 그동안 이런문제가 나오면, 나는 가로방향 for문 따로, 세로방향 for문 따로 문제를 풀어나갔다.

뭔가 머릿속으로는 비효율적이라는 생각은 했는데, 나은 방법이 떠오르지 않아서 그냥 이렇게 풀고 있었다.

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
board = [[0]*(m+2)]
for _ in range(n):
    board.append([0] + list(map(int, input().split())) + [0])
board.append([0]*(m+2))

ans = 0

# 가로방향
for i in range(1, n+1):
    val = 0
    for j in range(1, m+1):
        if board[i][j] > board[i][j+1]:
            val += board[i][j] - board[i][j+1]
    ans += val*2

# 세로방향
for j in range(1, m+1):
    val = 0
    for i in range(1, n+1):
        if board[i][j]  > board[i+1][j]:
            val += board[i][j] - board[i+1][j]
    ans += val*2

ans += n*m*2    

print(ans)

 

다른 사람의 코드도 봐보던 중  더 효율적으로 구현하는 방법을 찾았다

dx, dy를 이용해서 3중 for문으로 구현하는 것이다

 

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
board = [[0]*(m+2)]
for _ in range(n):
    board.append([0] + list(map(int, input().split())) + [0])
board.append([0]*(m+2))
            
ans = 0

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

for x in range(1, n+1):
    for y in range(1, m+1):
        ans += 2
        for i in range(4):
            nx, ny = x+dx[i], y+dy[i]
            
            if board[x][y] > board[nx][ny]:
                ans += board[x][y] - board[nx][ny]

print(ans)

반복문 하나에 동시에 가로,세로를 확인할 수 있었다.

이 코드 보니까 좀 그동안 이렇게 안한게 바보같이 느껴졌다

 

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

16931번: 겉넓이 구하기