쌓여있는 상자들의 겉넓이.

n*n 크기의 바닥에 각 변의 길이가 1인 상자들을 바닥이 보이지 않게 쌓았을 때, 상자들의 겉넓이의 합은? (단, 바닥에는 길이 1마다 눈금이 그려져 있으며, 상자는 눈금에 맞추어 쌓는다.)

추가: 겉넓이에는 바닥을 포함합니다.

입력 예: [[1,4,3,4], [2,3,4,1], [3,4,2,1], [9,3,2,1]]

입력 예에서 각 숫자는 해당 칸에 쌓인 상자의 개수이다.

출력: 120

+1 문제가 도저히 이해가 안갑니다. - 상파, 2016/04/20 00:17 M D
n*n 크기의 칸에 상자를 쌓았을 때 겉으로 드러나는 넓이를 뜻합니다. - Flair Sizz, 2016/04/21 13:05 M D
음.. >.< 입력 예 [[1,4,3,4], [2,3,4,1], [3,4,2,1], [9,3,2,1]] 는 그럼 무엇을 뜻하는 것인가요? - 상파, 2016/04/22 22:09 M D
[1,4,3,4] [2,3,4,1] [3,4,2,1] [9,3,2,1] 상파님 아마 이렇게 4X4크기를 나타내는것 같구 각 1X1들은 상자의 높이 인거 같네요.. 저도 한참 생각했습니다 ㅎㅎ.. - 이 우람, 2016/04/23 16:55 M D
아 그게 문제였군요. 수정하겠습니다. - Flair Sizz, 2016/04/23 21:22 M D
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

17개의 풀이가 있습니다. 1 / 2 Page

어렵겠다..라고 생각했는데 의외로 쉽게 풀리네요. 쌓여있는 상자들의 맨 아래 층부터 겉으로 드러난 옆면의 개수를 세고 위층으로 올라갑니다. 두 번째 층에서부터는 같은 식으로 옆면의 개수를 세면서 위로 드러난 면의 개수도 추가로 더합니다.

이를 위해서 2차원 배열의 각 값이 0보다 크면 상자가 있는 칸, 그렇지 않으면 상자가 없는 칸으로 간주하고 한 층의 옆/윗면을 다 세고 나면 모든 칸의 값을 1씩 빼고 위층으로 올라갑니다. 이 때 각 옆면이 겉면인지는 그 옆에 상자가 없으면 되는거죠.

다만, "쌓여있는 상자의 겉넓이"에서 바닥면의 면적을 더하는게 맞는지는 애매하네요.


def main(data):
    width = len(data[0])
    height = len(data)
    boxes = [[0] * width] * height

    for i, line in enumerate(data):
        boxes[i] = line

    level = 1
    result = 0

    def check_boxes():
        for story in boxes:
            if any([x >= 0 for x in story]):
                return True
        return False

    # 바닥개수 세기
    result += sum([sum([1 for y in x if y > 0]) for x in boxes])

    while check_boxes():
        sides = 0
        ups = 0
        for x in range(width):
            for y in range(height):
                if boxes[x][y] > 0: # 옆면의 개수 세기
                    if y == 0 or boxes[x][y-1] < 1:
                        sides += 1
                    if y == height - 1 or boxes[x][y+1] < 1:
                        sides += 1
                    if x == 0 or boxes[x-1][y] < 1:
                        sides += 1
                    if x == width - 1 or boxes[x+1][y] < 1:
                        sides += 1
        if level > 1: # 위로 드러난 면의 개수 세기
            ups = sum([sum([1 for y in x if y == 0]) for x in boxes])
        result += sides + ups
        level += 1
        boxes = [[y -1 for y in x] for x in boxes]
    return result
바닥면 더하는 것으로 수정하겠습니다. - Flair Sizz, 2016/04/21 13:00 M D
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

쌓여있는 상자더미를 위에서 바라봤을 때 각각의 칸으로 나눠서 옆넓이를 하나씩 하나씩 게산했습니다.

각 칸에서 그 칸 옆쪽에 상자가 원래칸보다 낮게 쌓여있을 경우, 두 높이의 차이가 그 쪽방향의 옆넓이입니다.
각 칸에서 그 칸 옆쪽에 상자가 원래칸보다 높게 쌓여있을 경우, 옆넓이는 0입니다.
각 칸에서 옆칸과의 차를 계산해서 양수이면 더해주고 음수이면 더해주지 않습니다.
옆칸이 상자가 쌓여있지 않은 바깥쪽이면 그냥 상자 높이가 그 쪽 옆면의 넓이입니다.

python 2.7

#-*- coding: utf-8 -*-
h = [[1,4,3,4], [2,3,4,1], [3,4,2,1], [9,3,2,1]]
res = 0
n = len(h)
m = len(h[0])
for i in range(n):
    for j in range(m):
        res += 2 # 상자더미의 맨 윗면과 맨 아랫면
        for (x,y) in [(0,1),(0,-1),(-1,0),(1,0)]:
            if i+x in range(n) and j+y in range(m):
                temp = h[i][j] - h[i+x][j+y]
                res += temp if temp > 0 else 0
            else :
                res += h[i][j]
print res
in 구문에서 iterable 쓸 수 있는 걸 오늘 처음 알았네요. 배워갑니다. - Flair Sizz, 2016/04/23 23:28 M D
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
sample = [[1,4,3,4],[2,3,4,1],[3,4,2,1],[9,3,2,1]]
class cube():
    def __init__(self, co_3):
        self.co_3 = co_3
        self.faceList = {'px':None,'nx':None,'py':None,'ny':None,'pz':None,'nz':None}
    def surface(self):
        result = 0
        for x in self.faceList.keys():
            if self.faceList[x] == None:
                result += 1
        return result

class space():
    def __init__(self, n):
        self.n = n
        self.cubemap = []
        self.newFloor('cube')
    def newFloor(self, fill = None):
        if fill == 'cube':
            self.cubemap.append(list(list(cube((0,y,x)) for x in range(self.n)) for y in range(self.n)))
        else:
            self.cubemap.append(list(list(None for x in range(self.n)) for y in range(self.n)))
    def addCube(self, co_2):
        y, x = co_2
        if self.cubemap[-1][y][x] != None:
            self.newFloor()
            self.cubemap[-1][y][x] = cube((len(self.cubemap)-1,y,x))
        else:
            for z in range(len(self.cubemap)):
                if self.cubemap[z][y][x] == None:
                    self.cubemap[z][y][x] = cube((z, y, x))
                    break
    def refresh(self, co_3):
        z, y, x = co_3
        c = self.cubemap
        #'px'
        if x < self.n-1 and type(c[z][y][x+1]) == cube:
            c[z][y][x+1].faceList['px'] = 1
        #'py'
        if y < self.n-1 and type(c[z][y+1][x]) == cube:
            c[z][y+1][x].faceList['py'] = 1
        #'pz'
        if z < len(c)-1 and type(c[z+1][y][x]) == cube:
            c[z+1][y][x].faceList['pz'] = 1
        #'nx'
        if type(c[z][y][x-1]) == cube and x > 0:
            c[z][y][x-1].faceList['nx'] = 1
        #'ny'
        if type(c[z][y-1][x]) == cube and y > 0:
            c[z][y-1][x].faceList['ny'] = 1
        #'nz'
        if type(c[z-1][y][x]) == cube and z > 0:
            c[z-1][y][x].faceList['nz'] = 1
    def cal(self):
        result = 0
        for z in self.cubemap:
            for y in z:
                for x in y:
                    if x != None:
                        self.refresh(x.co_3)
        for z in self.cubemap:
            for y in z:
                for x in y:
                    if x != None:
                        result += x.surface()
        return result

if __name__ == '__main__':
    sp = space(len(sample))
    for y, i in enumerate(sample):
        for x, j in enumerate(i):
            for k in range(j-1):
                sp.addCube((y, x))
    print(sp.cal())

파이썬 3.5.1

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

요즘 선형대수학을 공부중이어서 행렬의 개념으로 생각해봤습니다.

윗면 아랫면은 n제곱으로 구할 수 있으니 쉽고

전후좌우 면을 구해야 하는데요. 좀 생각해보면 '전후'와 '좌우'는 각각 겉넓이가 같습니다. 앞과 뒤에서 정면으로 물체를 바라본다 생각하면 보이는 모양이 (좌우 반전 정도는 있어도) 같지요. 그런 원리입니다.

그럼 전후 좌우는 어떻게 구하는지 생각을 좀 해봤는데요.

주어진 리스트를 행렬처럼 쓴다고 생각해보죠.(행렬을 표현하는 방법은 리스트의 리스트, 딕셔너리 등이 있지만 여기선 리스트로 구현)

X = [[1, 4, 3, 4], [2, 3, 4, 1], [3, 4, 2, 1], [9, 3, 2, 1]]

여기서 각 행들의 겉넓이를 구하고, 이 행 겉넓이의 합을 구하면 이것은 "그 방향에서 바라봤을 때의 겉넓이"가 됩니다.

즉 전후면 전후 방향의 겉넓이, 좌우면 좌우방향의 겉넓이가 되는거죠.

편의상 앞뒤를 구했다 생각하겠습니다.

그럼 좌우를 구해야죠? 좌우 방향은 주어진 행렬의 열과 행을 바꾸고(선형대수학에서는 transpose라고 합니다.)

다시 같은 방법으로 행들의 겉넓이를 구하면 됩니다.

결국 총 겉넓이는 위아래+앞뒤+좌우 겉넓이를 합치면 됩니다.

이러한 원리로 구현한 파이썬 코드입니다.

X = [[1, 4, 3, 4], [2, 3, 4, 1], [3, 4, 2, 1], [9, 3, 2, 1]]


def row_area(row_list):
    """각 row 의 겉넓이를 구하는 함수"""

    area0 = row_list[0]

    for j in range(len(row_list)-1):

        if row_list[j] < row_list[j+1]:
            area0 += (row_list[j+1]-row_list[j])
        else:
            pass

    return area0


def sum_row(matrix_list):
    """row_area 에서 구한 각 row의 겉넓이를 합치는 함수 """
    return sum(row_area(matrix_list[i]) for i in range(len(matrix_list)))

def transpose(matrix_x):
    """column area를 구하기 위해 matrix의 row와 column을 바꾸는 함수

    column_area는 matrix를 transpose 한 후 row_area를 구하는 과정으로 이루어진다.
    """
    matrix_y = [[0 for j in range(len(matrix_x[0]))] for i in range(len(matrix_x))]
    for i in range(len(matrix_x)):
        for j in range(len(matrix_x[0])):
            matrix_y[i][j] = matrix_x[j][i]

    return matrix_y

Y = transpose(X)

row_area_X = sum_row(X)
col_area_X = sum_row(Y)
floor_ceiling = len(X)**2

Total_area = 2*(row_area_X+col_area_X+floor_ceiling)

print(Total_area)
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

처음에는 보이는 면에 대해서만 계산을 하다보니 음영지역(?) 에 대한 계산이 어렵더군요.. 각 상자의 수에대해서 차이를 구하고 양수일 경우는 보이지 않는 부분 / 음수일 경우 보이는 부분으로 계산

    private int gen2(Integer[][] xx) {
        int area, tmp, sum = 0;
        for (Integer[] x : xx) {
            area = 0;
            for (int i = 0; i < x.length; i++) {
                tmp = (i == 0 ? -x[i] : x[i - 1] - x[i]);
                area += tmp > 0 ? 0 : tmp;
            }
            sum += Math.abs(area);
        }
        int upAndDown = (int) Math.pow(xx.length, 2) * 2;
        return sum*4 + upAndDown;
    }
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

Ruby

gap = ->a { a.flat_map {|e| [0,*e,0].each_cons(2).map {|a,b|(b-a).abs} } }
area = ->a { gap[a+a.transpose].sum + (a.size**2)*2 }

Test

expect( area[ [[1,2],
               [2,4]] ]).to eq 32
expect( area[ [[1,4,3,4],
               [2,3,4,1],
               [3,4,2,1],
               [9,3,2,1]]] ).to eq 120

Output

#=> puts area[ [[1,4,3,4],[2,3,4,1],[3,4,2,1],[9,3,2,1]] ]
120
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
data = [[0,0,0,0,0,0],
        [0,1,4,3,4,0],
        [0,2,3,4,1,0],
        [0,3,4,2,1,0],
        [0,9,3,2,1,0],
        [0,0,0,0,0,0]]


direction = [[-1,0],
             [1,0],
             [0,-1],
             [0,1]]

sum_area=0
for i in range(1,len(data)-1):
    for j in range(1,len(data[i])-1):
        for d in direction:
            di=d[0]
            dj=d[1]
            if data[i][j] > data[i+di][j+dj]:
                sum_area=sum_area + data[i][j] - data[i+di][j+dj]
        sum_area=sum_area+2
        print(sum_area)

print(sum_area)

파이썬 3입니다. 밑면 포함되는지 모르고 왜 답이 이상하게나오지 엄청 헤맸네요-_-ㅋㅋ 걍 단순하게 풀었습니다. 예외처리가 귀찮아서 배열을 0으로 둘러싸버렸네요..

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
 static void Main(string[] args)
        {
            int[] rectangls = new int[] { 1, 4, 3 ,4,2,3,4,1,3,4,2,1,9,3,2,1};
            int max = 0;
            foreach (int rect in rectangls)
            {
                if (max < rect)
                {
                    max = rect;
                }
            }
            string[,] rectdraw = new string[rectangls.Length, max];
            for (int i = 0; i < rectangls.Length; i++)
            {
                for (int x = 0; x < max; x++)
                {
                    rectdraw[i, max - x - 1] = "■";
                }
                for (int z = rectangls[i]; z < max; z++)
                {
                    rectdraw[i, max - z - 1] = "□";
                }
            }
            for (int y = 0; y < max; y++)
            {
                for (int x = 0; x < rectangls.Length; x++)
                {

                    Console.Write(rectdraw[x, y]);
                }
                Console.WriteLine();
            }
            int topbottom = rectangls.Length * 2;
            int side = 0;
            for (int i = 0; i < rectangls.Length; i++)
            {
                if (i == 0)
                {
                    side += rectangls[i];
                }
                if (i < rectangls.Length - 1)
                    side += Math.Abs(rectangls[i] - rectangls[i + 1]);
                if (i == rectangls.Length - 1)
                {
                    side += rectangls[i];
                }
            }
            Console.WriteLine(topbottom + side);
        }
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
>>> l = [[1,4,3,4], [2,3,4,1], [3,4,2,1], [9,3,2,1]]
>>> l + zip(*l)
[[1, 4, 3, 4], [2, 3, 4, 1], [3, 4, 2, 1], [9, 3, 2, 1], (1, 2, 3, 9), (4, 3, 4, 3), (3, 4, 2, 2), (4, 1, 1, 1)]
>>> inner = lambda l: sum(abs(x - y) for ll in l + zip(*l) for x, y in zip(ll, ll[1:]))
>>> inner(l)
39
>>> outer = lambda l: sum(x[0] + x[-1] for x in l + zip(*l))
>>> outer(l)
49
>>> flatten_metrix = [cell for cells in l for cell in cells]
>>> top_bottom_cnt = len(flatten_metrix) * 2 - flatten_metrix.count(0)
>>> inner(l) + outer(l) + top_bottom_cnt
120
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

안녕하세요. c++로 풀어봤습니다. 동서남북 네방향에서 반대방향으로 진행하면서 볼 수 있는 면들을 전부 더했습니다.

#include<iostream>

using namespace std;
void main()
{
    cout<<"Hello Stranger!!"<<endl;

    int input[4][4] =  {{1,4,3,4}, {2,3,4,1}, {3,4,2,1}, {9,3,2,1}};
    int res = 0;

    for(int i=0; i<4; i++)
    {
        int tmp1 = 0;
        int tmp2 = 0;

        for(int j=0; j<4; j++)
        {
            if( tmp1 < input[i][j] )
                res += input[i][j] - tmp1;

            tmp1 = input[i][j];

            if( tmp2 < input[j][i] )
                res += input[j][i] - tmp2;

            tmp2 = input[j][i];

            res++;
        }
        cout<<" : "<<res<<endl;
    }

    for(int i=3; i>=0; i--)
    {
        int tmp1 = 0;
        int tmp2 = 0;

        for(int j=3; j>=0; j--)
        {
            if( tmp1 < input[i][j] )
                res += input[i][j] - tmp1;

            tmp1 = input[i][j];

            if( tmp2 < input[j][i] )
                res += input[j][i] - tmp2;

            tmp2 = input[j][i];

            res++;
        }
    }

    cout<<res;

}

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

풀이 작성

※ 풀이작성 안내
  • 본문에 코드를 삽입할 경우 에디터 우측 상단의 "코드삽입" 버튼을 이용 해 주세요.
  • 마크다운 문법으로 본문을 작성 해 주세요.
  • 풀이를 읽는 사람들을 위하여 풀이에 대한 설명도 부탁드려요. (아이디어나 사용한 알고리즘 또는 참고한 자료등)
  • 작성한 풀이는 다른 사람(빨간띠 이상)에 의해서 내용이 개선될 수 있습니다.
목록으로
코딩도장

코딩도장은 프로그래밍 문제풀이를 통해서 코딩 실력을 수련(Practice)하는 곳입니다.


언어별 풀이 현황
전 체 x 17
python x 8
java x 3
ruby x 1
cs x 1
cpp x 1
matlab x 2
scala x 1