๐ ์ถ์ฒ - 1052-๋ฌผ๋ณ
๋ฌธ์ ์ค๋ช
์ง๋ฏผ์ด๋ N๊ฐ์ ๋ฌผ๋ณ์ ๊ฐ์ง๊ณ ์๋ค. ๊ฐ ๋ฌผ๋ณ์๋ ๋ฌผ์ ๋ฌดํ๋๋ก ๋ถ์ ์ ์๋ค. ์ฒ์์ ๋ชจ๋ ๋ฌผ๋ณ์๋ ๋ฌผ์ด 1๋ฆฌํฐ์ฉ ๋ค์ด์๋ค. ์ง๋ฏผ์ด๋ ์ด ๋ฌผ๋ณ์ ๋ ๋ค๋ฅธ ์ฅ์๋ก ์ฎ๊ธฐ๋ ค๊ณ ํ๋ค. ์ง๋ฏผ์ด๋ ํ ๋ฒ์ K๊ฐ์ ๋ฌผ๋ณ์ ์ฎ๊ธธ ์ ์๋ค. ํ์ง๋ง, ์ง๋ฏผ์ด๋ ๋ฌผ์ ๋ญ๋นํ๊ธฐ๋ ์ซ๊ณ , ์ด๋์ ํ ๋ฒ๋ณด๋ค ๋ง์ด ํ๊ธฐ๋ ์ซ๋ค. ๋ฐ๋ผ์, ์ง๋ฏผ์ด๋ ๋ฌผ๋ณ์ ๋ฌผ์ ์ ์ ํ ์ฌ๋ถ๋ฐฐํด์, K๊ฐ๋ฅผ ๋์ง ์๋ ๋น์ด์์ง ์์ ๋ฌผ๋ณ์ ๋ง๋ค๋ ค๊ณ ํ๋ค.
๋ฌผ์ ๋ค์๊ณผ ๊ฐ์ด ์ฌ๋ถ๋ฐฐ ํ๋ค.
๋จผ์ ๊ฐ์ ์์ ๋ฌผ์ด ๋ค์ด์๋ ๋ฌผ๋ณ ๋ ๊ฐ๋ฅผ ๊ณ ๋ฅธ๋ค. ๊ทธ ๋ค์์ ํ ๊ฐ์ ๋ฌผ๋ณ์ ๋ค๋ฅธ ํ ์ชฝ์ ์๋ ๋ฌผ์ ๋ชจ๋ ๋ถ๋๋ค. ์ด ๋ฐฉ๋ฒ์ ํ์ํ ๋งํผ ๊ณ์ ํ๋ค.
์ด๋ฐ ์ ์ฝ ๋๋ฌธ์, N๊ฐ๋ก K๊ฐ๋ฅผ ๋์ง์๋ ๋น์ด์์ง ์์ ๋ฌผ๋ณ์ ๋ง๋๋ ๊ฒ์ด ๋ถ๊ฐ๋ฅํ ์๋ ์๋ค. ๋คํํ๋, ์๋ก์ด ๋ฌผ๋ณ์ ์ด ์ ์๋ค. ์์ ์์ ์ฌ๋ ๋ฌผ๋ณ์ ๋ฌผ์ด 1๋ฆฌํฐ ๋ค์ด์๋ค.
์๋ฅผ ๋ค์ด, N=3์ด๊ณ , K=1์ผ ๋๋ฅผ ๋ณด๋ฉด, ๋ฌผ๋ณ 3๊ฐ๋ก 1๊ฐ๋ฅผ ๋ง๋๋ ๊ฒ์ด ๋ถ๊ฐ๋ฅํ๋ค. ํ ๋ณ์ ๋๋ค๋ฅธ ๋ณ์ ๋ถ์ผ๋ฉด, 2๋ฆฌํฐ๊ฐ ๋ค์ด์๋ ๋ฌผ๋ณ ํ๋์, 1๋ฆฌํฐ๊ฐ ๋ค์ด์๋ ๋ฌผ๋ณ ํ๋๊ฐ ๋จ๋๋ค. ๋ง์ฝ ์์ ์์ ํ ๊ฐ์ ๋ฌผ๋ณ์ ์ฐ๋ค๋ฉด, 2๋ฆฌํฐ๊ฐ ๋ค์ด์๋ ๋ฌผ๋ณ ๋ ๊ฐ๋ฅผ ๋ง๋ค ์ ์๊ณ , ๋ง์ง๋ง์ผ๋ก 4๋ฆฌํฐ๊ฐ ๋ค์ด์๋ ๋ฌผ๋ณ ํ ๊ฐ๋ฅผ ๋ง๋ค ์ ์๋ค.
์
๋ ฅ
์ฒซ์งธ ์ค์ N๊ณผ K๊ฐ ์ฃผ์ด์ง๋ค. N์ 107๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ์์ฐ์์ด๊ณ , K๋ 1,000๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ์์ฐ์์ด๋ค.
์ถ๋ ฅ
์ฒซ์งธ ์ค์ ์์ ์์ ์ฌ์ผํ๋ ๋ฌผ๋ณ์ ์ต์๊ฐ์ ์ถ๋ ฅํ๋ค. ๋ง์ฝ ์ ๋ต์ด ์์ ๊ฒฝ์ฐ์๋ -1์ ์ถ๋ ฅํ๋ค.
์ ์ถ๋ ฅ ์
์์ ์ ๋ ฅ | ์์ ์ถ๋ ฅ | |
---|---|---|
1 | 3 1 | 1 |
2 | 13 2 | 3 |
3 | 1000000 5 | 15808 |
์ด ๋ฌธ์ ๋ ๊ตฌ๊ธ๋งํด์ ์ ๋ฐํ ํ์ด๋ฅผ ์ ํ๊ฒ ๋ผ ๊ทธ๋ ๊ฒ ํ๋ฒ ํ์ด๋ดค๋ค.
์ผ๋จ 1~8๊น์ง์ ์ซ์๋ฅผ ์ด์ง์๋ก ๋ํ๋์ ๋, ์ด์ง์์์ 1์ด ๋ํ๋ด๋ ๊ฐ์๊ฐ ๊ณง ์ฌ์ค์ง ์๊ณ ์ฎ๊ธธ ์ ์๋ ๋ณ์ ๊ฐ์๊ฐ ๋๊ฒ ๋๋ค.
๋ฐ๋ผ์ K๋ฅผ ์ด๊ณผํ์ง ์๋๋ค๋ฉด ๊ด์ฐฎ์ง๋ง, ๋ง์ฝ ์ด๊ณผํ๋ค๋ฉด ๋ฌผ๋ณ์ ๋ ์ฌ์์ ์ฎ๊ฒจ ๋ด์์ผ ํ๋ค.
- N์ ์ด์ง์๋ก ๋ณ๊ฒฝํ์ ๋ 1์ ๊ฐ์๋ฅผ ์นด์ดํธ ํด K๊ฐ ์ด๊ณผํ ๋ ๋ฐ๋ณต๋ฌธ์ ์คํํด์ค๋ค.
- N์ 2์ง์๋ก ๋ณ๊ฒฝํ์ฌ ์ฒ์ 1์ด ๋ํ๋๋ ์์น๋ฅผ ์ฐพ๊ณ
- ํด๋น ์์น๋ฅผ P๋ผ๊ณ ํ์ ๋, 2^P๋งํผ answer์ N์ ๋ํ๋ค.
- answer์ ๋ํ๋ ๊ฒ์ ์ฌ์จ ๋ฌผ๋ณ์ ๊ฐ์
- N์๋ k๊ฐ ์ดํ๋ก ๋ง๋ค๊ธฐ ์ํด ๋ํ๋ ๊ฒ์ด๋ค.
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
answer = 0
while bin(N).count('1') > K:
plus = 2 ** (bin(N)[::-1].index('1'))
answer += plus
N += plus
print(answer)