๐ ์ถ์ฒ - 2164-์นด๋2
๋ฌธ์ ์ค๋ช
N์ฅ์ ์นด๋๊ฐ ์๋ค. ๊ฐ๊ฐ์ ์นด๋๋ ์ฐจ๋ก๋ก 1๋ถํฐ N๊น์ง์ ๋ฒํธ๊ฐ ๋ถ์ด ์์ผ๋ฉฐ, 1๋ฒ ์นด๋๊ฐ ์ ์ผ ์์, N๋ฒ ์นด๋๊ฐ ์ ์ผ ์๋์ธ ์ํ๋ก ์์๋๋ก ์นด๋๊ฐ ๋์ฌ ์๋ค.
์ด์ ๋ค์๊ณผ ๊ฐ์ ๋์์ ์นด๋๊ฐ ํ ์ฅ ๋จ์ ๋๊น์ง ๋ฐ๋ณตํ๊ฒ ๋๋ค. ์ฐ์ , ์ ์ผ ์์ ์๋ ์นด๋๋ฅผ ๋ฐ๋ฅ์ ๋ฒ๋ฆฐ๋ค. ๊ทธ ๋ค์, ์ ์ผ ์์ ์๋ ์นด๋๋ฅผ ์ ์ผ ์๋์ ์๋ ์นด๋ ๋ฐ์ผ๋ก ์ฎ๊ธด๋ค.
์๋ฅผ ๋ค์ด N=4์ธ ๊ฒฝ์ฐ๋ฅผ ์๊ฐํด ๋ณด์. ์นด๋๋ ์ ์ผ ์์์๋ถํฐ 1234 ์ ์์๋ก ๋์ฌ์๋ค. 1์ ๋ฒ๋ฆฌ๋ฉด 234๊ฐ ๋จ๋๋ค. ์ฌ๊ธฐ์ 2๋ฅผ ์ ์ผ ์๋๋ก ์ฎ๊ธฐ๋ฉด 342๊ฐ ๋๋ค. 3์ ๋ฒ๋ฆฌ๋ฉด 42๊ฐ ๋๊ณ , 4๋ฅผ ๋ฐ์ผ๋ก ์ฎ๊ธฐ๋ฉด 24๊ฐ ๋๋ค. ๋ง์ง๋ง์ผ๋ก 2๋ฅผ ๋ฒ๋ฆฌ๊ณ ๋๋ฉด, ๋จ๋ ์นด๋๋ 4๊ฐ ๋๋ค.
N์ด ์ฃผ์ด์ก์ ๋, ์ ์ผ ๋ง์ง๋ง์ ๋จ๊ฒ ๋๋ ์นด๋๋ฅผ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
์
๋ ฅ
์ฒซ์งธ ์ค์ ์ ์ N(1 โค N โค 500,000)์ด ์ฃผ์ด์ง๋ค.
์ถ๋ ฅ
์ฒซ์งธ ์ค์ ๋จ๊ฒ ๋๋ ์นด๋์ ๋ฒํธ๋ฅผ ์ถ๋ ฅํ๋ค.
์ ์ถ๋ ฅ ์
์์ ์ ๋ ฅ | ์์ ์ถ๋ ฅ | |
---|---|---|
6 | 4 |
Logic 1
์ ์ผ ๋จผ์ ์ ๊ทผํ๋ ๋ฐฉ๋ฒ์ QUEUE์ด๋ค.
๋ฌธ์ ์ ๋์์๋ ๊ทธ๋๋ก ํ๋ฅผ ์ด์ฉํด ํ์๋๋ ๋ฐ๋ก ํด๊ฒฐ์ด ๊ฐ๋ฅํ๋ค.
ํ์ง๋ง ์ด ๋ฐฉ๋ฒ์ ์๊ฐ์ด๊ณผ๊ฐ ๋ฌ ์ฝ๋์ด๋ค.
๊ทธ๋์ ๊ฒฝ์ฐ์ ์๋ฅผ 1/4๊น์ง ์ค์ฌ๋ดค์ง๋ง ๋ง์ฐฌ๊ฐ์ง๋ก ์๊ฐ์ด๊ณผ๊ฐ ๊ณ์ ๋ฌ๋ค.
Logic 2
๋ ๋ฒ์งธ ์ ๊ทผํ๋ ๋ฐฉ๋ฒ์collections์ deque
์ ์ด์ฉํด๋ดค๋ค. ์ด ๋ฐฉ๋ฒ์ ์ด์ฉํ๋ฉด ์๊ฐ์ด๊ณผ๊ฐ ๋จ์ง ์๋๋ค. ์ฝ๋๋ ์์ ์ฝ๋์ ๋น์ทํ๋ค.
deque๋ '๋ฑ'์ด๋ผ๊ณ ํ๋ฉฐ Double Ended Queue์ ์ฝ์์ด๋ค. ํ์ ์คํ์ ๋ ๋ค ๋ง๋ค ์ ์๋ ์๋ฃ๊ตฌ์กฐ์ธ๋ฐ, ์ ๋๋จ์์ ๋ชจ๋ push์ pop์ด ๊ฐ๋ฅํ๋ค.
ํ์ด์ฌ์์ collections ๋ชจ๋ ์์ deque๋ CPython์ผ๋ก ๊ตฌ์ฑ๋์ด ์์ด์ ์๋๋ฉด์์ ํจ์ฌ ๋น ๋ฅด๋ค๊ณ ํ๋ค.
Logic 3
๋ง์ง๋ง์ผ๋ก ์ผ์ ํ ๊ท์น์ ๋ฐ๊ฒฌํด ๊ณต์์ ์ฐพ๊ฒ ๋๋ฉด ์๊ฐ ๋ณต์ก๋ ์ธก๋ฉด์์ ์ฐ์๋ฅผ ์ฐจ์งํ ์ ์๋ค ์๊ฐ๋ค์ด ๋์ ํด๋ณธ ๋ฐฉ๋ฒ์ ๋๋ค.
-- | Input | Output |
---|---|---|
2 | 2 | |
3 | 2 | |
4 | 4 | |
5 | 2 | |
6 | 4 | |
7 | 6 | |
8 | 8 |
์์ ๊ฐ์ด Input์ด ์ฃผ์ด์ก์ ๋, Output๋ ์์ ๊ฐ์ด ๋์ค๊ฒ ๋ฉ๋๋ค.
์์ ํน์ง์ ๋ถ์ํด ๋ณธ ๊ฒฐ๊ณผ ์๋์ ๊ฐ์ ํน์ง์ ๋๋ ๊ฒ์ ๋ฐ๊ฒฌํ์ต๋๋ค.
3์ผ ๋ : (3 - 2) * 2 = 2
4์ผ ๋ : (4 - 2) * 2 = 4
5์ผ ๋ : (5 - 4) * 2 = 2
6์ผ ๋ : (6 - 4) * 2 = 4
7์ผ ๋ : (7 - 4) * 2 = 6
8์ผ ๋ : (8 - 4) * 2 = 8
>>> [ Input - 2**(Input > 2์ ์ ๊ณฑ) ] * 2
N = int(input())
cardList = [i for i in range(1, N+1)]
while len(cardList) > 1:
cardList.pop(0)
cardList.append(cardList.pop(0))
print(cardList[0])
from collections import deque
N = int(input())
deque = deque([i for i in range(1, N+1)])
while len(deque) > 1:
deque.popleft()
deque.append(deque.popleft())
print(deque[0])
import sys
input = sys.stdin.readline
N = int(input())
square = 2
while True:
if (N == 1 or N == 2):
print(N)
break
square *= 2
if (square >= N):
print((N - (square // 2)) * 2)
break
๊ธฐ๋ณธ์ ์ธ ํจ์๋ค์ ์ฌ๊ธฐ์ ํ์ธํ๋ฉด ๋๋ค.