백준 - 14719번 빗물 python 문제풀이 [Hellfer]

728x90

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

14719번: 빗물

첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치

www.acmicpc.net

🔷 알고리즘 분류 - 구현, 시뮬레이션 난이도 - 골드 5

1. input(): 사용자로부터 입력을 받는 함수입니다.

이 함수는 문자열을 반환하며, 이를 여러 개의 변수에 할당하거나 숫자로 변환하기 위해 종종 split()과 int()와 함께 사용됩니다.

2. split(): 문자열을 특정 구분자를 기준으로 분리하여 리스트로 반환하는 함수입니다.

인자가 없는 경우 공백을 기준으로 분리합니다.

3. int(): 문자열이나 실수를 정수로 변환하는 함수입니다.

이 함수는 input()으로 입력받은 문자열을 정수로 변환하는 데에 주로 사용됩니다.

4. map(): 첫 번째 인자로 주어진 함수를 두 번째 인자로 주어진 반복 가능한 객체의 모든 항목에 적용하고, 그 결과를 반복자로 반환하는 함수입니다.

이 함수는 각 입력 값을 특정 타입으로 변환하거나, 모든 항목에 특정 연산을 적용하는 데에 주로 사용됩니다.

5. list(): 반복 가능한 객체를 리스트로 변환하는 함수입니다.

이 함수는 map()의 결과를 리스트로 변환하는 데에 주로 사용됩니다.

5. max(): 인자로 주어진 두 개 이상의 숫자 중에서 가장 큰 값을 반환하는 함수입니다.

이 함수는 두 개의 값 중 더 큰 값을 찾는 데에 사용됩니다.

6. min(): 인자로 주어진 두 개 이상의 숫자 중에서 가장 작은 값을 반환하는 함수입니다.

이 함수는 두 개의 값 중 더 작은 값을 찾는 데에 사용됩니다.

7. print(): 인자로 주어진 값을 출력하는 함수입니다. 이 함수는 결과를 화면에 출력하는 데에 사용됩니다.

🔶문제 풀이 - 구현을 이용한 풀이

n,m=map(int,input().split()) # n과 m은 각각 가로와 세로의 길이를 의미합니다.
x=list(map(int,input().split())) # x는 각 위치의 높이를 저장하는 배열입니다.

a=[0]*(m) # a는 왼쪽에서부터 각 위치까지의 최대 높이를 저장하는 배열입니다.
a[0]=x[0] # 첫 번째 위치의 최대 높이는 첫 번째 위치의 높이와 같습니다.
for i in range(1,m): # 각 위치에 대해
    a[i]=max(a[i-1], x[i]) # 현재 위치의 최대 높이는 이전 위치의 최대 높이와 현재 위치의 높이 중 더 큰 값입니다.
    
b=[0]*(m) # b는 오른쪽에서부터 각 위치까지의 최대 높이를 저장하는 배열입니다.
b[-1]=x[-1] # 마지막 위치의 최대 높이는 마지막 위치의 높이와 같습니다.
for i in range(m-2,-1,-1): # 각 위치에 대해 (오른쪽에서 왼쪽으로)
    b[i]=max(b[i+1],x[i]) # 현재 위치의 최대 높이는 다음 위치의 최대 높이와 현재 위치의 높이 중 더 큰 값입니다.
    
result=0 # result는 총 빗물의 양을 저장하는 변수입니다.
for i in range(m): # 각 위치에 대해
    result+=min(a[i],b[i])-x[i] # 현재 위치에서 쌓일 수 있는 빗물의 양은 왼쪽과 오른쪽에서의 최대 높이 중 작은 값에서 현재 높이를 뺀 값입니다.
    
print(result) # 총 빗물의 양을 출력합니다.

🔶 문제 이해하기

다음과 같은 높이 배열이 있다고 가정해 보겠습니다.

4 4
3 0 1 4

위의 배열은 높이 4의 장벽 사이에 높이 공간이 있는 구조를 나타냅니다.

이 경우, 각 위치에서 빗물이 얼마나 쌓일 수 있는지 계산해 보겠습니다.

먼저, 각 위치에서 왼쪽 방향으로 가장 높은 장벽의 높이를 찾으면 다음과 같습니다.

3 3 3 3

그다음, 각 위치에서 오른쪽 방향으로 가장 높은 장벽의 높이를 찾으면 다음과 같습니다.

4 4 4 4

이 두 높이 중 더 낮은 높이에서 현재 위치의 높이를 빼면 다음과 같습니다.

0 3 2 0

즉, 높이가 "3 0 1 4"인 경우, 빗물이 총 5만큼 쌓일 수 있음을 알 수 있습니다.