๐Ÿงฉ Problem Solving/[๋ฐฑ์ค€]

[๋ฐฑ์ค€] 18111 ๋งˆ์ธํฌ๋ž˜ํ”„ํŠธ (python ํŒŒ์ด์ฌ)

์ œ๋ด‰์•„ 2022. 6. 23. 12:36

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

 

18111๋ฒˆ: ๋งˆ์ธํฌ๋ž˜ํ”„ํŠธ

ํŒ€ ๋ ˆ๋“œ์‹œํ”„ํŠธ๋Š” ๋Œ€ํšŒ ์ค€๋น„๋ฅผ ํ•˜๋‹ค๊ฐ€ ์ง€๋ฃจํ•ด์ ธ์„œ ์ƒŒ๋“œ๋ฐ•์Šค ๊ฒŒ์ž„์ธ ‘๋งˆ์ธํฌ๋ž˜ํ”„ํŠธ’๋ฅผ ์ผฐ๋‹ค. ๋งˆ์ธํฌ๋ž˜ํ”„ํŠธ๋Š” 1 × 1 × 1(์„ธ๋กœ, ๊ฐ€๋กœ, ๋†’์ด) ํฌ๊ธฐ์˜ ๋ธ”๋ก๋“ค๋กœ ์ด๋ฃจ์–ด์ง„ 3์ฐจ์› ์„ธ๊ณ„์—์„œ ์ž์œ ๋กญ๊ฒŒ

www.acmicpc.net


์•„์ด๋””์–ด

1. ๋ธŒ๋ฃจํŠธ ํฌ์Šค

  • ๋ฌธ์ œ์—์„œ ๋†’์ด ์ด๊ฐ€ 256๊นŒ์ง€ ๊ทธ๋ฆฌ๊ณ  N, M์ด 500๊นŒ์ง€๊ฐ€ ์ตœ๋Œ€๋‹ค.
  • 256*500*500 = 64000000์ด๋ฏ€๋กœ 1์ดˆ ์•ˆ์— ๊ฐ€๋Šฅํ•˜๋‹ค ์ƒ๊ฐ..

2. ์‹œ๊ฐ„ ์ดˆ๊ณผ

  • ๋ธŒ๋ฃจํŠธ ํฌ์Šค๋กœ ๊ฐ€๋Šฅํ•˜๋‹ค ์ƒ๊ฐํ–ˆ๋Š”๋ฐ ๊ณ„์† ์‹œ๊ฐ„ ์ดˆ๊ณผ๊ฐ€ ๊ฑธ๋ ธ๋‹ค.
  • ๋‹ค๋ฅธ ์‚ฌ๋žŒ๋“ค์ด ์ง  ์ฝ”๋“œ๋ฅผ ํ™•์ธํ•ด ๋ณด๋‹ˆ elif๊ฐ€ ์•„๋‹Œ else๋ฅผ ์‚ฌ์šฉํ–ˆ๋‹ค.
  • pypy๋กœ ํ†ต๊ณผํ–ˆ๋‹ค.
  • else์™€ elif๊ฐ€ ์‹œ๊ฐ„ ์ฐจ์ด๊ฐ€ ๋งŽ์ด ๋‚œ๋‹ค๋Š” ๊ฒƒ์„ ์ฒ˜์Œ ์•Œ์•˜๋‹ค.

 


์ฝ”๋“œ ์„ค๋ช…

for i in range(257): #๋•… ๋†’์ด
    use_block = 0
    take_block = 0
    for x in range(N):
        for y in range(M):
            if block[x][y] > i:
                take_block += block[x][y] - i
            else:
                use_block += i - block[x][y]

    if use_block > take_block + B:
        continue

    count = take_block * 2 + use_block

    if count <= ans:
        ans = count
        glevel = i

๊ฐ ๋„๋‹ฌํ•˜๊ณ  ์‹ถ์€ ๋†’์ด๋งˆ๋‹ค 2์ฐจ์› ๋ฆฌ์ŠคํŠธ๋ฅผ ํƒ์ƒ‰ํ•ด์ค€๋‹ค.

 

๋ธ”๋ก ๋†’์ด์™€ ๋„๋‹ฌ ๋†’์ด๋ฅผ ๋น„๊ตํ•ด๊ฐ€๋ฉฐ ๊ฐ€์ ธ์˜จ ๋ธ”๋ก(take_block), ์‚ฌ์šฉํ•œ ๋ธ”๋Ÿญ(use_block)์— ๋ธ”๋Ÿญ ๊ฐœ์ˆ˜๋ฅผ ์ถ”๊ฐ€ํ•ด์ค€๋‹ค.

์ดํ›„ ์ด ์‚ฌ์šฉํ•œ ๋ธ”๋ก๊ณผ ๊ฐ€์ ธ์˜จ ๋ธ”๋ก + ์›๋ž˜ ์žˆ๋˜ ๋ธ”๋Ÿญ ๊ฐœ์ˆ˜๋ฅผ ๋น„๊ตํ•ด์„œ ๋„๋‹ฌ ๋†’์ด๋กœ ๋งŒ๋“œ๋Š” ๊ฒŒ ๊ฐ€๋Šฅํ•œ์ง€ ํ™•์ธํ•œ๋‹ค.

 

๊ฐ€๋Šฅํ•˜๋‹ค๋ฉด ๊ฑธ๋ฆฌ๋Š” ์‹œ๊ฐ„์„ ๊ณ„์‚ฐํ•˜๊ณ  ์ตœ์†Ÿ๊ฐ’ ๋น„๊ต๋ฅผ ํ•ด์ค€๋‹ค.

 


์ „์ฒด ์ฝ”๋“œ

import sys
N, M, B = map(int,input().split())
block = []
for _ in range(N):
    block.append([int(x) for x in sys.stdin.readline().rstrip().split()])

ans = int(1e9)
glevel = 0

for i in range(257): #๋•… ๋†’์ด
    use_block = 0
    take_block = 0
    for x in range(N):
        for y in range(M):
            if block[x][y] > i:
                take_block += block[x][y] - i
            else:
                use_block += i - block[x][y]

    if use_block > take_block + B:
        continue

    count = take_block * 2 + use_block

    if count <= ans:
        ans = count
        glevel = i

print(ans, glevel)

else๋ณด๋‹ค elif ๊ฐ€ ์—ฐ์‚ฐ์„ ๋” ํ•˜๋‹ˆ๊นŒ ์‹œ๊ฐ„์ด ๋” ๊ฑธ๋ฆฐ๋‹ค๊ณ ๋Š” ์ƒ๊ฐํ–ˆ์ง€๋งŒ ์‹œ๊ฐ„ ์ดˆ๊ณผ๊ฐ€ ๋œฐ ์ •๋„๋กœ ์ฐจ์ด ๋‚ ์ค„ ๋ชฐ๋ž๋‹ค.

๊ณจ๋“œ ์ด์ƒ ๋ฌธ์ œ๋“ค์„ ํ’€๋‹ค ๋ณด๋ฉด ์ด๋Ÿฐ ์‹์œผ๋กœ ์‹œ๊ฐ„ ์ดˆ๊ณผ๊ฐ€ ๋„ˆ๋ฌด ์ž์ฃผ ๋‚˜์˜จ๋‹ค. cpp๋กœ ๋„˜์–ด๊ฐˆ๊นŒ ๊ณ ๋ฏผ.