ํ์ด
๊ทธ๋ฆฌ๋ ์๊ณ ๋ฆฌ์ฆ ๋ฌธ์ ์ ๋๋ค. ์๊ฐ๋ณด๋ค ์ค๋ ๊ฑธ๋ ธ์ต๋๋ค. ์ฒ์์๋ ์ํ๊ฐ ๋์ ํ์ดํ์ ์ขํ(?)๋ฅผ ๋ด๋ฆผ์ฐจ์์ผ๋ก ์ ๋ ฌํด์ ๋ค์์๋ถํฐ ๊ณ ์ณ๋๊ฐ๋ ๊ฒ์ ์๊ฐํ๋๋ฐ์. ์ ๊ทธ๋ ๊ฒ ์๊ฐํ๋์ง ์์ํ ์ ๋๋ก ์ด๋ก ์ธํด ์ฝ๋๊ฐ ๋ณต์กํด์ก์์ต๋๋ค.
๊ฐ์ธ์ ์ธ ์๊ฐ์ผ๋ก๋ ๋ค์์ ์ฝ๋๋ ์ ๋ต์ ๊ฐ๊น๊ฒ ์ง๋ง, ์ด๋์์ ๊ฐ ์น๋ช ์ ์ธ ์ค์๋ฅผ ํ๊ณ ์๋ ๋ฏ ํฉ๋๋ค. ๊ด๋ จํ์ฌ ๋๋ฒ๊น ์ ํด์ฃผ์ค ๋ถ ์์ผ์๋ฉด ํ๊ฒฝํฉ๋๋ค.
- ์คํจ ์ฝ๋
n, l = map(int, input().split(' '))
arr = list(map(int, input().split(' ')))
arr.sort(reverse=True)
tmpl = l # ํ์ฌ ํ
์ดํ
loc = arr[0] # ํ์ฌ ํ
์ดํ๋ฅผ ๋ถ์ด๊ธฐ ์์ํ๋ ์์น
ans = 1 # ์ฌ์ฉํ ํ
์ดํ์ ๊ฐฏ์
for i in range(1, n) :
# ํ์ฌ ํ
์ดํ๋ฅผ ์ฌ์ฉํ๋ ค๊ณ ์๋ํ๋ค.
tmpl -= (loc - arr[i] + 1)
# ๋ง์ฝ ํ
์ดํ๋ฅผ ๋ค ์ฐ๊ฒ๋๋ค๋ฉด
if(tmpl <= 0) :
tmpl = l # ์๋ก ํ
์ดํ๋ฅผ ๊บผ๋ด๊ณ
ans += 1 # ์ฌ์ฉํ ํ
์ดํ์ ๊ฐฏ์ +=1
loc = arr[i] # ํ์ฌ ์์น๋ถํฐ ๋ค์ ํ
์ดํ๋ฅผ ๋ถ์ธ๋ค.
print(ans)
์ ๋ค 0.5 ๊ฐ๊ฒฉ์ ์ฒ์์๋ ๊ณ ๋ คํ์ง ์์๋ค๊ฐ, tmpl -= (loc - arr[i] + 1)
๋ก ๋ฌด๋งํ๋ ค ํ ๋ถ๋ถ์์ ๋ญ๊ฐ ๊ฒฝ๊ณ๊ฐ ์๋ฌ๊ฐ ๋ฐ์ํ๋ค๊ณ ์ถ์ ํฉ๋๋ค. ๋ง์ง๋ง์ผ๋ก ๊ธฐ์ตํ๋ ๊ฒ์ ๊ฐ๋ น ์ธํ์ผ๋ก 4 2 1 2 3 100 ์ด ๋ค์ด์ค๋ฉด, ๋ถ๋ช
3์ ์ถ๋ ฅํด์ผ ํ๋๋ฐ 2๋ฅผ ์ถ๋ ฅํ์ต๋๋ค.
๋จ์ถ๋ถํฐ ์๋ชป ๋ผ์ด ํด๋น ์ฝ๋๋ฅผ ์ง์ํ๋๋? ์๋๋ฉด ๊ทธ๋ฅ ์ค๋ฆ์ฐจ์์ผ๋ก ์์ํด์ ๋จธ๋ฆฟ ์์ ์๊ณ ๋ฆฌ์ฆ์ ๊ทธ๋๋ก ๋ฐ์์ ๋๋ ์ค ํ์๋ฅผ ์ ํํ์ฌ ํด๊ฒฐํ์ต๋๋ค.
- ์ ๋ต ์ฝ๋
n, l = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort()
tapeL = 0 # ์ด์ด์ง๋ ๊ตฌ๋ฉ๋ค์ ๋ฉ์ฐ๊ธฐ ์ํด ์ง๊ธ๊น์ง ์ฌ์ฉํ ํ
์ดํ์ ๊ธธ์ด
ans = 1 # ์ฌ์ฉํ ํ
์ดํ์ ๊ฐฏ์
for i in range(1,n) :
recL = arr[i]-arr[i-1]
tapeL += recL
if(tapeL >= l) :
ans += 1
tapeL = 0
print(ans)
์๊ณ ๋ฆฌ์ฆ
- ํ์ฌ ๊ตฌ๋ฉ๊ณผ ๊ทธ ๋ค์ ๊ตฌ๋ฉ์ ๊ฐ๊ฒฉ์ ๋ฐ์ ํ(
recL = arr[i]-arr[i-1]
), ๊ทธ ๊ฐ๊ฒฉ๋งํผ ํ ์ดํ๋ฅผ ๋ถ์ด๋ ค ์๋(tapeL += recL
)ํฉ๋๋ค. - ๋ถ๊ฐ๋ฅํ ๊ฒฝ์ฐ(
tapeL >= 1
, ์ฆ ๋ถ์ด๋ ค ์๋ํ๋๋ฐ ์ ํด์ง ํ ์ดํ์ ๊ธธ์ด๋ฅผ ๋์ด์๋ ๊ฒฝ์ฐ(tapeL>l
)์ ์ ํํ ๊ทธ ํ ์ดํ๋ฅผ ๋ค ์ด ๊ฒฝ์ฐ(tapeL==l
), - ํ
์ดํ๋ฅผ ํ๋ ๋ ๊บผ๋ด๊ณ (
ans+=1
) ํ์ฌ๊น์ง ์ฌ์ฉํ ํ ์ดํ์ ๊ธธ์ด๋ฅผ ์ด๊ธฐํ(tapeL = 0
)ํด์ค๋๋ค.