πŸ”—https://www.acmicpc.net/problem/2468

문제


μž¬λ‚œλ°©μž¬μ²­μ—μ„œλŠ” λ§Žμ€ λΉ„κ°€ λ‚΄λ¦¬λŠ” μž₯λ§ˆμ² μ— λŒ€λΉ„ν•΄μ„œ λ‹€μŒκ³Ό 같은 일을 κ³„νšν•˜κ³  μžˆλ‹€. λ¨Όμ € μ–΄λ–€ μ§€μ—­μ˜ 높이 정보λ₯Ό νŒŒμ•…ν•œλ‹€. κ·Έ λ‹€μŒμ— κ·Έ 지역에 λ§Žμ€ λΉ„κ°€ 내렸을 λ•Œ 물에 μž κΈ°μ§€ μ•ŠλŠ” μ•ˆμ „ν•œ μ˜μ—­μ΄ μ΅œλŒ€λ‘œ λͺ‡ κ°œκ°€ λ§Œλ“€μ–΄ μ§€λŠ” μ§€λ₯Ό μ‘°μ‚¬ν•˜λ €κ³  ν•œλ‹€. μ΄λ•Œ, 문제λ₯Ό κ°„λ‹¨ν•˜κ²Œ ν•˜κΈ° μœ„ν•˜μ—¬, μž₯λ§ˆμ² μ— λ‚΄λ¦¬λŠ” λΉ„μ˜ 양에 따라 μΌμ •ν•œ 높이 μ΄ν•˜μ˜ λͺ¨λ“  지점은 물에 μž κΈ΄λ‹€κ³  κ°€μ •ν•œλ‹€.

μ–΄λ–€ μ§€μ—­μ˜ 높이 μ •λ³΄λŠ” ν–‰κ³Ό μ—΄μ˜ 크기가 각각 N인 2차원 λ°°μ—΄ ν˜•νƒœλ‘œ μ£Όμ–΄μ§€λ©° λ°°μ—΄μ˜ 각 μ›μ†ŒλŠ” ν•΄λ‹Ή μ§€μ μ˜ 높이λ₯Ό ν‘œμ‹œν•˜λŠ” μžμ—°μˆ˜μ΄λ‹€. 예λ₯Ό λ“€μ–΄, λ‹€μŒμ€ N=5인 μ§€μ—­μ˜ 높이 정보이닀.

image.png

이제 μœ„μ™€ 같은 지역에 λ§Žμ€ λΉ„κ°€ λ‚΄λ €μ„œ 높이가 4 μ΄ν•˜μΈ λͺ¨λ“  지점이 물에 μž κ²Όλ‹€κ³  ν•˜μž. 이 κ²½μš°μ— 물에 μž κΈ°λŠ” 지점을 νšŒμƒ‰μœΌλ‘œ ν‘œμ‹œν•˜λ©΄ λ‹€μŒκ³Ό κ°™λ‹€.

image.png

물에 μž κΈ°μ§€ μ•ŠλŠ” μ•ˆμ „ν•œ μ˜μ—­μ΄λΌ 함은 물에 μž κΈ°μ§€ μ•ŠλŠ” 지점듀이 μœ„, μ•„λž˜, 였λ₯Έμͺ½ ν˜Ήμ€ μ™Όμͺ½μœΌλ‘œ 인접해 있으며 κ·Έ 크기가 μ΅œλŒ€μΈ μ˜μ—­μ„ λ§ν•œλ‹€. μœ„μ˜ κ²½μš°μ—μ„œ 물에 μž κΈ°μ§€ μ•ŠλŠ” μ•ˆμ „ν•œ μ˜μ—­μ€ 5κ°œκ°€ λœλ‹€(κΌ­μ§“μ μœΌλ‘œλ§Œ λΆ™μ–΄ μžˆλŠ” 두 지점은 μΈμ ‘ν•˜μ§€ μ•ŠλŠ”λ‹€κ³  μ·¨κΈ‰ν•œλ‹€).

λ˜ν•œ μœ„μ™€ 같은 μ§€μ—­μ—μ„œ 높이가 6μ΄ν•˜μΈ 지점을 λͺ¨λ‘ 잠기게 λ§Œλ“œλŠ” λ§Žμ€ λΉ„κ°€ 내리면 물에 μž κΈ°μ§€ μ•ŠλŠ” μ•ˆμ „ν•œ μ˜μ—­μ€ μ•„λž˜ κ·Έλ¦Όμ—μ„œμ™€ 같이 λ„€ κ°œκ°€ 됨을 확인할 수 μžˆλ‹€.

image.png

이와 같이 μž₯λ§ˆμ² μ— λ‚΄λ¦¬λŠ” λΉ„μ˜ 양에 λ”°λΌμ„œ 물에 μž κΈ°μ§€ μ•ŠλŠ” μ•ˆμ „ν•œ μ˜μ—­μ˜ κ°œμˆ˜λŠ” λ‹€λ₯΄κ²Œ λœλ‹€. μœ„μ˜ μ˜ˆμ™€ 같은 μ§€μ—­μ—μ„œ λ‚΄λ¦¬λŠ” λΉ„μ˜ 양에 λ”°λ₯Έ λͺ¨λ“  경우λ₯Ό λ‹€ 쑰사해 보면 물에 μž κΈ°μ§€ μ•ŠλŠ” μ•ˆμ „ν•œ μ˜μ—­μ˜ 개수 μ€‘μ—μ„œ μ΅œλŒ€μΈ κ²½μš°λŠ” 5μž„μ„ μ•Œ 수 μžˆλ‹€.

μ–΄λ–€ μ§€μ—­μ˜ 높이 정보가 μ£Όμ–΄μ‘Œμ„ λ•Œ, μž₯λ§ˆμ² μ— 물에 μž κΈ°μ§€ μ•ŠλŠ” μ•ˆμ „ν•œ μ˜μ—­μ˜ μ΅œλŒ€ 개수λ₯Ό κ³„μ‚°ν•˜λŠ” ν”„λ‘œκ·Έλž¨μ„ μž‘μ„±ν•˜μ‹œμ˜€.

μ œν•œ

image.png

문제 해석