๋ฐฑ์ค 2847 : ๊ฒ์์ ๋ง๋ ๋์ค์ด
ํ์ด
(1) ๋ชจ๋ ๋ ๋ฒจ์ ํญ์ ๋์ฐจ์๋ ์ค๋ฆ์ฐจ์์ด ๋์ด์ผ ํฉ๋๋ค. (2) ๋จ, ๋์ฐจ์๋ ์ค๋ฆ์ฐจ์์ ๋ง๋ค๊ธฐ ์ํด ํน์ ๋ ๋ฒจ์ ์ฆ๊ฐ์ํค๋ ๋์ ๊ฐ์์์ผ์ ์ค๋ฆ์ฐจ์์ผ๋ก ๋ฐ๊พธ์ด์ค๋๋ค.
ํ ์คํธ์ผ์ด์ค
- ์ฒ์ level
4 5 3 7 5
- ๋ฐ๋ level
2 3 4 5
- ์ถ๋ ฅ
6
ํด๋น ์์ ํ ์คํธ์ผ์ด์ค๋ก๋ถํฐ level[i-1]์ ํญ์ level[i]๋ณด๋ค ์์์ผ ํ๋ค๊ณ ์๊ฐํ๊ณ , ์ต์ํ์ผ๋ก ๊ฐ์์์ผ์ผ ํ๋ฏ๋ก ์ ํํ 1๋ง ์์ผ๋ฉด ๋๋ค๊ณ ์๊ฐํ์ต๋๋ค.
- ์ฒ์ level
4 5 3 7 4
- ๋ฐ๋ level
1 2 3 4
- ์ถ๋ ฅ
9
์์ ํ ์คํธ์ผ์ด์ค๋ ํ๋๋ง ๋ฐ๊ฟ๋ณผ๊น ์ถ์ด์ ๋ฃ์ด๋ณธ ํ ์คํธ์ผ์ด์ค์ธ๋ฐ, ์ด์ข๊ฒ ์ข์ ์ผ์ด์ค๊ฐ ์ ๋ ฅ๋์์ต๋๋ค. ์์ ์ ๋ ฅ์ ๋ค์์ ์์๋ก 1 2 3 4 ๋ก ๋ฐ๋์ด์ผ ํ ๋ฏ ํฉ๋๋ค.
5 3 7 4
2 3 3 4
1 2 3 4
์ด ๋์์ ๊ตฌํํด์ฃผ๊ธฐ ์ํด์ (1) level์ด ๋์ฐจ ์๋ ์ค๋ฆ์ฐจ์์ผ๋ก ์ ๋ ฌ๋์ด์๋์ง ์ฌ๋ถ๋ฅผ ํ์ ํ๋ ํจ์๋ฅผ ๋ง๋ค์ด์ฃผ์๊ณ , (2) level[i-2]๊ฐ level[i-1]๊ณผ ๊ฐ์ ๊ฒฝ์ฐ์๋ level[i-2]์์ ํ๋๋ฅผ ๋นผ์ฃผ๋ if๋ฌธ์ ์ถ๊ฐํ์ต๋๋ค.
์ฝ๋
def isSorted(arr) :
for i in range(1,len(arr)) :
if(arr[i-1] < arr[i]) :
continue
else :
return False
return True
N = int(input())
level = []
for _ in range(N) :
level.append(int(input()))
ans = 0
while(isSorted(level) is False) :
for i in range(1, N) :
if(level[i-1] >= level[i]) :
origin = level[i-1]
level[i-1] = level[i]-1
diff = origin - level[i-1]
ans += diff
if(i >= 2 and level[i-2] == level[i-1]) :
level[i-2] -= 1
ans += 1
print(ans)
์ฝ๋๋ฆฌ๋ทฐ
ํด๋น ๋ธ๋ก๊ทธ์ ๊ฒ์๋ฌผ์ ํ์ธํด๋ณด๊ณ ์ ์ฝ๋์์ ์ฐจ์ด๋ฅผ ์ฐพ์๋ณด์์ต๋๋ค.
- for i in range(N-1, 0, -1)
- range๋
range(์์ ์ซ์, ์ข ๋ฃ ์ซ์, step)
์ผ๋ก ์ด๋ฃจ์ด์ง๋๋ค. ์ฆ ์์ ์ฝ๋๋ ๋ฐฐ์ด์ ์ญ์์ผ๋ก ์ดํด๋ณด๊ณ ์์ต๋๋ค. - ์ ์ฝ๋์ ๊ฒฝ์ฐ์๋ ์์์๋ถํฐ ๊ฐ์์์ผ์ฃผ๋๋ผ, ์๊ณผ ํ์ฌ์์ ๋์ฐจ๊ฐ ๋ฐ์ํ๊ณ ์์์ต๋๋ค.
- ๋ค์์๋ถํฐ ๋ณธ๋ค๋ฉด, ๊ฐ์๋ง์ ์ฌ์ฉํ๊ณ ์์ผ๋ฏ๋ก ๋์ฐจ๊ฐ ๋ฐ์ํ์ง ์์ ๊ฒ์ ๋๋ค. ์ง์ ํ ๊ทธ๋ฆฌ๋์ ๋๋ค.
- ๋ง์ฝ ์ฆ๊ฐ๋ฅผ ์ฌ์ฉํด์ ์ค๋ฆ์ฐจ์์ผ๋ก ๋ง๋ ๋ค๋ฉด, ์์์๋ถํฐ ๋ณด๋๊ฒ ๋ง๊ฒ ์ต๋๋ค. ๋ฌด์กฐ๊ฑด ์ง์ ์ ์๋ณด๋ค ํฌ๋ฉด ๋ฐ๋์ ์ค๋ฆ์ฐจ์์ผ๋ก ์ ๋ ฌ๋๊ธฐ ๋๋ฌธ์ ๋๋ค.
- ์ ์ฝ๋์ ๊ฒฝ์ฐ์๋ ์์์๋ถํฐ ๋ณด๋ฉฐ, ์์ ๋ฐฐ์ด๊ฐ๊ณผ ํ์ฌ๊ฐ์ ๋น๊ตํ๊ณ ์์์ต๋๋ค. ์ด ๊ฒฝ์ฐ์๋ ๋ฌด์กฐ๊ฑด ์์ ์๋ณด๋ค ์๋ค๊ณ ํด์ ์ง์ ์ ์๋ณด๋ค ํฌ๋ค๋ ๋ณด์ฆ์ด ์์๊ธฐ๋ ๊น๋ญ์ ๋๋ค.
- ์ฆ๊ฐ์ธ์ง, ๊ฐ์์ธ์ง, ์ค๋ฆ์ฐจ์์ธ์ง, ๋ด๋ฆผ์ฐจ์์ธ์ง์ ๋ํด ์๊ณ ๋ฆฌ์ฆ์ด ํ์คํ๊ฒ ๋ฌ๋ผ์ง๊ณ , ํจ์จ์ฑ๋ ๋ฌ๋ผ์ง ์ ์๋ค๋ ์ ์ ๋ฐฐ์ ์ต๋๋ค.
- range๋