[백준] 14719번 (python 파이썬)

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

 

구현 문제이다.

 

해당 블록에 대한 2차원 배열을 생성하였다.

배열은 그림에서 90도 회전한 것처럼 만들었다.

1	1	1	0
1	0	0	0
1	1	0	0
1	1	1	0
1	1	1	1
1	0	0	0
1	0	0	0
1	1	0

 

열을 하나씩 보면서 처음 1이 나왔을때부터 count를 1씩 증가시켰고 다음 1이 나오면 정답에 더해줬다.

만약 처음에 1이 나온시점부터 다음에 1이 나오지 않았다면 0을 더해준다.

 

from collections import deque

h, w = map(int, input().split(' '))
blocks = deque(list(map(int, input().split(' '))))

graph = [[0] * h for _ in range(w)]

for i in range(w):
    block = blocks.popleft()
    for j in range(block):
        graph[i][j] = 1


answer = 0
for j in range(h):
    first_block = False
    sub_answer = 0
    for i in range(w):
        if not first_block and graph[i][j] == 1:
            first_block = True
            continue

        if first_block and graph[i][j] == 0:
            sub_answer += 1
            continue

        if first_block and graph[i][j] == 1:
            answer += sub_answer
            sub_answer = 0

print(answer)

 

 

두번째 구현한 방법은

2차원 배열을 사용하지 않았다.

 

세로 길이 만큼 반복하면서

해당 블록의 높이가 현재 세로보다 큰지 확인하고 클 경우

다음 블록까지 해당 높이보다 작을 때는 카운트를 증가시켜줬고

다음 블록이 현재 세로보다 클경우 계산한 카운트를 정답에 더해줬다.

 

처음 구현한 것과 방식은 동일하지만 2차원 배열을 사용하지 않고 블럭의 높이만 보고 계산

 

h, w = map(int, input().split(' '))
blocks = list(map(int, input().split(' ')))

answer = 0
for i in range(h):
    first_block = False
    sub_answer = 0
    for j in range(w):
        if not first_block and blocks[j] > i:
            first_block = True
            continue

        if first_block and blocks[j] <= i:
            sub_answer += 1
            continue

        if first_block and blocks[j] > i:
            answer += sub_answer
            sub_answer = 0

print(answer)