๋ฌธ์
https://www.acmicpc.net/problem/1011
๋ฐฑ์ค ๋ฌธ์ ์ง - 0x12๊ฐ - ์ํ
์๊ณ ๋ฆฌ์ฆ: ์ํ
ํ์ด
ํ์นํ๊ฒ ๋ ์ฐ์ฃผ์ ์ Alpha Centauri๋ผ๋ ์๋ก์ด ์ธ๋ฅ์ ๋ณด๊ธ์๋ฆฌ๋ฅผ ๊ฐ์ฒํ๊ธฐ ์ํ ๋๊ท๋ชจ ์ํ ์ ์ง ์์คํ ์ ํ์ฌํ๊ณ ์๊ธฐ ๋๋ฌธ์, ๊ทธ ํฌ๊ธฐ์ ์ง๋์ด ์์ฒญ๋ ์ด์ ๋ก ์ต์ ๊ธฐ์ ๋ ฅ์ ์ด ๋์ํ์ฌ ๊ฐ๋ฐํ ๊ณต๊ฐ์ด๋ ์ฅ์น๋ฅผ ํ์ฌํ์๋ค. ํ์ง๋ง ์ด ๊ณต๊ฐ์ด๋ ์ฅ์น๋ ์ด๋ ๊ฑฐ๋ฆฌ๋ฅผ ๊ธ๊ฒฉํ๊ฒ ๋๋ฆด ๊ฒฝ์ฐ ๊ธฐ๊ณ์ ์ฌ๊ฐํ ๊ฒฐํจ์ด ๋ฐ์ํ๋ ๋จ์ ์ด ์์ด์, ์ด์ ์๋์๊ธฐ์ k๊ด๋ ์ ์ด๋ํ์์ ๋๋ k-1 , k ํน์ k+1 ๊ด๋ ๋ง์ ๋ค์ ์ด๋ํ ์ ์๋ค. ์๋ฅผ ๋ค์ด, ์ด ์ฅ์น๋ฅผ ์ฒ์ ์๋์ํฌ ๊ฒฝ์ฐ -1 , 0 , 1 ๊ด๋ ์ ์ด๋ก ์ ์ด๋ํ ์ ์์ผ๋ ์ฌ์ค์ ์์ ํน์ 0 ๊ฑฐ๋ฆฌ๋งํผ์ ์ด๋์ ์๋ฏธ๊ฐ ์์ผ๋ฏ๋ก 1 ๊ด๋ ์ ์ด๋ํ ์ ์์ผ๋ฉฐ, ๊ทธ ๋ค์์๋ 0 , 1 , 2 ๊ด๋ ์ ์ด๋ํ ์ ์๋ ๊ฒ์ด๋ค. ( ์ฌ๊ธฐ์ ๋ค์ 2๊ด๋ ์ ์ด๋ํ๋ค๋ฉด ๋ค์ ์๊ธฐ์ 1, 2, 3 ๊ด๋ ์ ์ด๋ํ ์ ์๋ค. )
๊ณต๊ฐ์ด๋ ์ฅ์น ์๋์์ ์๋์ง ์๋ชจ๊ฐ ํฌ๋ค๋ ์ ์ ์ ์๊ณ ์๊ธฐ ๋๋ฌธ์ x์ง์ ์์ y์ง์ ์ ํฅํด ์ต์ํ์ ์๋ ํ์๋ก ์ด๋ํ๋ ค ํ๋ค. ํ์ง๋ง y์ง์ ์ ๋์ฐฉํด์๋ ๊ณต๊ฐ ์ด๋์ฅ์น์ ์์ ์ฑ์ ์ํ์ฌ y์ง์ ์ ๋์ฐฉํ๊ธฐ ๋ฐ๋ก ์ง์ ์ ์ด๋๊ฑฐ๋ฆฌ๋ ๋ฐ๋์ 1๊ด๋ ์ผ๋ก ํ๋ ค ํ๋ค.
๊น์ฐํ์ ์ํด x์ง์ ๋ถํฐ ์ ํํ y์ง์ ์ผ๋ก ์ด๋ํ๋๋ฐ ํ์ํ ๊ณต๊ฐ ์ด๋ ์ฅ์น ์๋ ํ์์ ์ต์๊ฐ์ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ๋ผ.
์ฌ์ค ๊ฐ์ด ์กํ๋ฏ ๋ง๋ฏ ํด์ ํค๋งค๊ณ ์์๋๋ฐ, ์ง๋ฌธ๊ฒ์ํ์ ๊ฑฐ์ ๋ต์ง์ ๊ฐ์ ๋ฐ๋ก๊ฐ ์์๋ค.
https://www.acmicpc.net/board/view/128555
๊ฑฐ๋ฆฌ๊ฐ 1์ผ๋๋ถํฐ ํ๋์ฉ ๊ณ์ฐํด๋ณด๋ฉด ์ด๋ ํ์๋ ๋ค์๊ณผ ๊ฐ๋ค.
# ๊ฑฐ๋ฆฌ = ์ด๋ํ์
1 = 1
2 = 2
3, 4 = 3
5, 6 = 4
7, 8, 9 = 5
10, 11, 12 = 6
13, 14, 15, 16 = 7
17, 18, 19, 20 = 8
...
๊ทธ๋ฆฌ๊ณ ๊ฐ ์ด๋ํ์์ ๋ฐ๋ณต์ด ๋ช๋ฒ์ฉ ๋ฐ์ํ๋์ง ๊ณ์ฐํด๋ณด๋ฉด 1, 1, 2, 2, 3, 3, 4, 4... ์ ๊ฐ๋ค.
์ฆ ์ด๋ํ์์ ๋ฐ๋ณต์ ๋๋ฒ์ฉ์ด๋ค.
๋ํ ์ด๋ํ์์ ํด๋น๋๋ ๊ฑฐ๋ฆฌ ์ค ๋ง์ง๋ง ๊ฑฐ๋ฆฌ๋ค์ ๊ฐ์ ๊ณ์ฐํด๋ณด๋ฉด ์๋์ ๊ฐ๋ค.
1 = 1
2 = 1 + 1
4 = 1 + 1 + 2
6 = 1 + 1 + 2 + 2
9 = 1 + 1 + 2 + 2 + 3
12 = 1 + 1 + 2 + 2 + 3 + 3
...
๋ฐ๋ผ์ ๋งค ํด๋ง๋ค ํด์ ํ์๋ฅผ ์นด์ดํธํ๋ฉฐ ๊ฑฐ๋ฆฌ๊ฐ์ ๊ณ์ฐํ๋ค. 1๋ถํฐ ๋๋ฒ์ฉ ๋ฐ๋ณตํด์ ๋ํด์ฃผ๊ณ (1, 1, 2, 2, 3, 3...), ๊ทธ ๊ฐ์ด ์ฐพ๊ณ ์ ํ๋ ๊ฑฐ๋ฆฌ๊ฐ์ ๋์ด์๊ฑฐ๋ ๊ฐ์์ง๋ฉด ๋ฐ๋ณต๋ฌธ์ ๋น ์ ธ๋์จ๋ค.
์๋ฅผ๋ค์ด ์ฐพ๊ณ ์ ํ๋ ๊ฑฐ๋ฆฌ๊ฐ 10์ด๋ผ๋ฉด, 1 + 1 + 2 + 2 + 3 + 3 ๊น์ง ๊ตฌํ ๋ค ๋น ์ ธ๋์ค๊ณ ์นด์ดํธํ ๊ฐ 6์ ์ถ๋ ฅํ๊ฒ ๋๋๊ฒ์ด๋ค.
์ข ์ฝ๊ฒ ํ์ด์ฐ๋ฉด ๊ฑฐ๋ฆฌ๊ฐ ๋์ด๋จ์ ๋ฐ๋ผ ์ด๋ํ์๊ฐ ๊ฒน์น๋ ์ซ์(๊ฑฐ๋ฆฌ)๋ค์ ์๋ ๋ง์์ง๋๋ฐ, ๊ทธ ์ซ์๋ค์ ๊ฐฏ์๊ฐ 1, 1, 2, 2, 3, 3... ์ด๋ฐ์์ผ๋ก ๋์ด๋๋ ํํ๋ค. ๊ทธ๋ฌ๋ฏ๋ก ๊ฐ ์ด๋ํ์์ ํฌํจ๋๋ ๊ฑฐ๋ฆฌ ์์ ๋ด๊ฐ ์ฐพ๊ณ ์ ํ๋ ๊ฑฐ๋ฆฌ๊ฐ ํฌํจ๋ ๋๊น์ง ๊ฑฐ๋ฆฌ๋ฅผ ๋๋ ค๊ฐ๋ค.
์ ์ฒด ์ฝ๋
# ๋ฉ๋ชจ๋ฆฌ: 32412KB / ์๊ฐ: 1308ms
from sys import stdin
input = stdin.readline
for _ in range(int(input())):
x, y = map(int, input().split())
distance = y - x # ๊ฑฐ๋ฆฌ
curr_dis = 1 # ์ด๋๊ฑฐ๋ฆฌ
total_dis = 0 # ์ง๊ธ๊น์ง ์ด๋ํ ๊ฑฐ๋ฆฌ
move_cnt = 0 # ์ด๋ํ์
while total_dis < distance:
total_dis += curr_dis
move_cnt += 1
if move_cnt % 2 == 0: # curr_dis๋งํผ์ ์ด๋์ 2๋ฒ ๋ฐ๋ณตํ๋ค๋ฉด curr_dis๋ฅผ ์ฆ๊ฐ์ํด
curr_dis += 1
print(move_cnt)
์ํ... ์ง๊ธ๋ถํฐ๋ผ๋ ๋ค์ ๊ณต๋ถํ์...