๋ฌธ์
https://www.acmicpc.net/problem/1744
๋ฐฑ์ค ๋ฌธ์ ์ง - 0x11๊ฐ - ๊ทธ๋ฆฌ๋
์๊ณ ๋ฆฌ์ฆ: ๊ทธ๋ฆฌ๋, ์ ๋ ฌ
ํ์ด
๋ฌธ์ ๊ธธ์ด๊ฐ N์ธ ์์ด์ด ์ฃผ์ด์ก์ ๋, ๊ทธ ์์ด์ ํฉ์ ๊ตฌํ๋ ค๊ณ ํ๋ค. ํ์ง๋ง, ๊ทธ๋ฅ ๊ทธ ์์ด์ ํฉ์ ๋ชจ๋ ๋ํด์ ๊ตฌํ๋ ๊ฒ์ด ์๋๋ผ, ์์ด์ ๋ ์๋ฅผ ๋ฌถ์ผ๋ ค๊ณ ํ๋ค. ์ด๋ค ์๋ฅผ ๋ฌถ์ผ๋ ค๊ณ ํ ๋, ์์น์ ์๊ด์์ด ๋ฌถ์ ์ ์๋ค. ํ์ง๋ง, ๊ฐ์ ์์น์ ์๋ ์(์๊ธฐ ์์ )๋ฅผ ๋ฌถ๋ ๊ฒ์ ๋ถ๊ฐ๋ฅํ๋ค. ๊ทธ๋ฆฌ๊ณ ์ด๋ค ์๋ฅผ ๋ฌถ๊ฒ ๋๋ฉด, ์์ด์ ํฉ์ ๊ตฌํ ๋ ๋ฌถ์ ์๋ ์๋ก ๊ณฑํ ํ์ ๋ํ๋ค.
์๋ฅผ ๋ค๋ฉด, ์ด๋ค ์์ด์ด {0, 1, 2, 4, 3, 5}์ผ ๋, ๊ทธ๋ฅ ์ด ์์ด์ ํฉ์ ๊ตฌํ๋ฉด 0+1+2+4+3+5 = 15์ด๋ค. ํ์ง๋ง, 2์ 3์ ๋ฌถ๊ณ , 4์ 5๋ฅผ ๋ฌถ๊ฒ ๋๋ฉด, 0+1+(2*3)+(4*5) = 27์ด ๋์ด ์ต๋๊ฐ ๋๋ค.
์์ด์ ๋ชจ๋ ์๋ ๋จ ํ๋ฒ๋ง ๋ฌถ๊ฑฐ๋, ์๋๋ฉด ๋ฌถ์ง ์์์ผํ๋ค.
์์ด์ด ์ฃผ์ด์ก์ ๋, ์์ด์ ๊ฐ ์๋ฅผ ์ ์ ํ ๋ฌถ์์ ๋, ๊ทธ ํฉ์ด ์ต๋๊ฐ ๋๊ฒ ํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
์์ ๋ฒ์๋ -1,000 ~ 1,000 ์ด๋ค.
๋ฐ๋ผ์ ์์์ ์์๊ฐ ์์ฌ์๋ ์์ด์ด ์ฃผ์ด์ง ์๋ ์์ผ๋ฏ๋ก ์กฐ๊ฑด๋ถ๊ธฐ๋ฅผ ํ์คํ ํด์ผํ๋ค.
๋จผ์ ์์ด์ ์ค๋ฆ์ฐจ์์ผ๋ก ์ ๋ ฌ ํ ์์, ์์, 0, 1 ๋ก ๋ถ๋ฆฌ์ํจ๋ค. ๊ทธ๋ผ ๋ถ๋ฆฌ์ํจ ํญ๋ชฉ๋ค์ ์์ฐ์ค๋ฝ๊ฒ ์ค๋ฆ์ฐจ์์ด ๋๋ค.
์ต๋๊ฐ์ ๋ง๋ค๊ธฐ์ํ ์กฐ๊ฑด์ ์๋์ ๊ฐ๋ค.
- ์์๋ ์ต๋ํ 0์ ๊ฐ๊น๊ฒ, ํน์ ์์๋ก ๋ง๋ค์ด์ค๋ค.
- ์์๋ ํฐ ๊ฐ๋ผ๋ฆฌ ๊ณฑํด์ค๋ค.
- 0์ ์์์๋ ์ฌ์ฉํ์ง ์๋๋ค. ์์์ ์ง์ง์ด์ ์์์ํค๊ฑฐ๋ ์ฌ์ฉํ์ง ์๋๋ค.
- 1์ ๊ทธ๋๋ก ๋๋ค.
1. ์์๊ฐ ์ฒ๋ฆฌ
๊ฐฏ์์ ๋ฐ๋ผ ์คํ๊ฐ์ด ๋ฌ๋ผ์ง๋ค.
ํ์๊ฐ, ํ๊ฐ ์กด์ฌํ ๊ฒฝ์ฐ๋ 0์ ์ ๋ฌด์ ๋ฐ๋ผ ๋ถ๋ฆฌ๋๋ค.
1) ์ง์๊ฐ ์กด์ฌํ ๊ฒฝ์ฐ: ์์๋๋ก ๋๊ฐ์ฉ ๋ฌถ์ด ๊ณฑํด์ค ๋ค ๊ฒฐ๊ณผ๊ฐ์ ๋ํด์ค๋ค.
2) ํ์๊ฐ ์กด์ฌํ ๊ฒฝ์ฐ: ์ ์ผ ํฐ ๊ฐ(์์์ ๊ฐ๊น์ด ๊ฐ)์ ์ ์ธํ๊ณ ์์๋๋ก ๋๊ฐ์ฉ ๊ณฑํด์ค๋ค.
- 0์ด ์์๊ฒฝ์ฐ: ์์ ์ ์ผ ํฐ ๊ฐ๊ณผ 0์ ๊ณฑํด 0์ผ๋ก ๋ง๋ค์ด์ค ๋ค 0์ ๊ฐฏ์๋ฅผ ๊ฐ์์ํจ๋ค.
- 0์ด ์์๊ฒฝ์ฐ: ๊ทธ๋๋ก ๊ฒฐ๊ณผ๊ฐ์ ๋ํด์ค๋ค.
3) ํ ๊ฐ ์กด์ฌํ ๊ฒฝ์ฐ
- 0์ด ์์๊ฒฝ์ฐ: 0๊ณผ ๊ณฑํด์ค์ 0์ผ๋ก ๋ง๋ค์ด์ค ๋ค 0์ ๊ฐฏ์๋ฅผ ๊ฐ์์ํจ๋ค.
- 0์ด ์์๊ฒฝ์ฐ: ๊ทธ๋๋ก ๊ฒฐ๊ณผ๊ฐ์ ๋ํด์ค๋ค.
2. ์์๊ฐ ์ฒ๋ฆฌ
์์ ์ญ์ ๊ฐฏ์์ ๋ฐ๋ผ ์คํ๊ฐ์ด ๋ฌ๋ผ์ง๋ค.
๋จ, 0์ ์์์๋ ์ฌ์ฉํ์ง ์์ผ๋ฏ๋ก ์์๊ฐ์ด 1๊ฐ์ธ ๊ฒฝ์ฐ๋ ์ฒดํฌํ์ง ์๋๋ค.
1) ์ง์๊ฐ ์กด์ฌํ ๊ฒฝ์ฐ: ์์๋๋ก ๋๊ฐ์ฉ ๋ฌถ์ด ๊ณฑํด์ค ๋ค ๊ฒฐ๊ณผ๊ฐ์ ๋ํด์ค๋ค.
2) ํ์๊ฐ ์กด์ฌํ ๊ฒฝ์ฐ: ์ ์ผ ์์๊ฐ์ ๊ทธ๋๋ก ๋ํด์ฃผ๊ณ , ๋๋จธ์ง๋ ๋๊ฐ์ฉ ๋ฌถ์ด ๊ณฑํด์ค๋ค.
3. ๋๋จธ์ง
์ฌํ๊น์ง์ ๊ฒฐ๊ณผ๊ฐ์ 1์ ๊ฐฏ์๋งํผ์ ๋ํด์ค๋ค.
0์ ์์ ์ฒ๋ฆฌ ์ธ์ ๊ณ์ฐํ ํ์ ์์ผ๋ฏ๋ก ๋์ด๊ฐ๋ค.
์ ์ฒด ์ฝ๋
# ๋ฉ๋ชจ๋ฆฌ: 32412KB / ์๊ฐ: 36ms
from sys import stdin
input = stdin.readline
N = int(input())
nums = [int(input()) for _ in range(N)]
nums.sort()
ret = 0
minus = []
plus = []
zero = 0
one = 0
for n in nums:
if n < 0:
minus.append(n)
elif n == 0:
zero += 1
elif n == 1:
one += 1
else:
plus.append(n)
# 1. ์์๊ฐ ์ฒ๋ฆฌ
if minus:
if len(minus) % 2 == 0:
for i in range(0, len(minus), 2):
ret += minus[i] * minus[i+1]
elif len(minus) == 1:
if zero > 0:
zero -= 1
else:
ret += minus[0]
else:
for i in range(0, len(minus)-1, 2):
ret += minus[i] * minus[i+1]
if zero > 0:
zero -= 1
else:
ret += minus[-1]
# 2. ์์๊ฐ ์ฒ๋ฆฌ
if plus:
if len(plus) % 2 == 0:
for i in range(0, len(plus), 2):
ret += plus[i] * plus[i+1]
else:
for i in range(len(plus)-1, 0, -2):
ret += plus[i] * plus[i-1]
ret += plus[0]
# 3. ๋๋จธ์ง
print(ret + one)
ํผ์ง์ปฌ ๋ฌธ์ ์ ๊ฐ๊น๋ค. ์๋ํ๋ฉด ๋ค๋ฅธ ๊ฐ์ด ๋์ค๋ฏ๋ก ์กฐ๊ฑด ์์ฑ์ ์ฃผ์ํด์ผํ๋ค.