๋ฌธ์
https://www.acmicpc.net/problem/1038
๋ฐฑ์ค ๋ฌธ์ ์ง - 0x12๊ฐ - ์ํ
์๊ณ ๋ฆฌ์ฆ: ์ํ, ๋ฐฑํธ๋ํน, ๋ธ๋ฃจํธํฌ์ค
ํ์ด
์์ด ์๋ ์ ์ X์ ์๋ฆฟ์๊ฐ ๊ฐ์ฅ ํฐ ์๋ฆฟ์๋ถํฐ ์์ ์๋ฆฟ์๊น์ง ๊ฐ์ํ๋ค๋ฉด, ๊ทธ ์๋ฅผ ๊ฐ์ํ๋ ์๋ผ๊ณ ํ๋ค. ์๋ฅผ ๋ค์ด, 321๊ณผ 950์ ๊ฐ์ํ๋ ์์ง๋ง, 322์ 958์ ์๋๋ค. N๋ฒ์งธ ๊ฐ์ํ๋ ์๋ฅผ ์ถ๋ ฅํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค. 0์ 0๋ฒ์งธ ๊ฐ์ํ๋ ์์ด๊ณ , 1์ 1๋ฒ์งธ ๊ฐ์ํ๋ ์์ด๋ค. ๋ง์ฝ N๋ฒ์งธ ๊ฐ์ํ๋ ์๊ฐ ์๋ค๋ฉด -1์ ์ถ๋ ฅํ๋ค.
๊ฐ์ํ๋ ์๊ฐ ๋๋ ค๋ฉด ์์ ์ผ์ชฝ๋ถํฐ ์ค๋ฅธ์ชฝ๊น์ง ๋ด๋ฆผ์ฐจ์์ด์ด์ผ ํ๋ค.
์๋ฅผ๋ค์ด,
11, 352, 901 → ๊ฐ์ํ๋ ์ X
10, 521, 910 → ๊ฐ์ํ๋ ์ O
๋ฐ๋ผ์ 0 ~ 9 ์ ์ซ์๋ก ๋ง๋ค ์ ์๋ ๊ฐ์ํ๋ ์์ ์ต๋๊ฐ์ 9876543210 ์ด๋ค.
์ฆ 1์๋ฆฌ๋ถํฐ 10์๋ฆฌ๊น์ง ๋ฐฑํธ๋ํน or ์กฐํฉ์ ์ฌ์ฉํ์ฌ ๊ฐ์ํ๋ ์๋ฅผ ์์ฑํ๊ณ , ๋ฆฌ์คํธ์ ์ถ๊ฐํ๋ค.
for i in range(1, 11):
for j in combinations(range(9, -1, -1), i):
num = "".join(list(map(str, list(j))))
ret.append(int(num))
combinations ๋ชจ๋์ ์ฌ์ฉํ๋ฉด ์ฐธ์กฐํ ๋ฆฌ์คํธ์ ์ฒซ๋ฒ์งธ ์์๋ถํฐ ์์๋๋ก ์กฐํฉ์ ์์ฑํ๋ฏ๋ก, 98, 97... 87, 86... ์์ผ๋ก ์์ฐ์ค๋ฝ๊ฒ ๊ฐ์ํ๋ ์ ํํ๋ฅผ ๋๊ฒ ๋๋ค.
๋ชจ๋ ๊ตฌํ๋ค๋ฉด ๋ฆฌ์คํธ๋ฅผ ์ค๋ฆ์ฐจ์์ผ๋ก ์ ๋ ฌ ํ ๋ฆฌ์คํธ์ ๊ธธ์ด๊ฐ N ์ด์์ด๋ผ๋ฉด -1์, ์๋๋ผ๋ฉด N๋ฒ์งธ ๊ฐ์ ์ถ๋ ฅํ๋ค.
์ ๋ณด๋ฉด ๊ฐ์ํ๋ ์์ ์๋ฒ์ 1๋ถํฐ ๊ณ์ฐํ๋๊ฒ์ด ์๋ 0๋ถํฐ ๊ณ์ฐํ๊ธฐ ๋๋ฌธ์ด๋ค.
๋ง์ฝ 8๋ฒ์งธ ๊ฐ์ํ๋ ์๋ฅผ ๊ตฌํ๊ณ ์ ํ๋๋ฐ ๋ฆฌ์คํธ๊ฐ ์๋์ ๊ฐ์ด ๊ตฌ์ฑ๋์ด์๋ค๊ณ ์๊ฐํด๋ณด๋ฉด,
ret = [0, 1, 2, 3, 4, 5, 6, 7]
๋ฆฌ์คํธ์ ๊ธธ์ด๊ฐ 8์ด์ง๋ง ์กฐ๊ฑด์ ๋ง์กฑํ์ง ๋ชปํ๋ค.
๋ฐ๋ผ์ ๋ฆฌ์คํธ์ ๊ธธ์ด๊ฐ ์ต์ N + 1์ผ๊ฒฝ์ฐ์๋ง N๋ฒ์งธ ๊ฐ์ํ๋ ์๋ฅผ ๊ตฌํ ์ ์๋ค.
์ ์ฒด ์ฝ๋
1. combinations ๋ชจ๋ ์ฌ์ฉ
# ๋ฉ๋ชจ๋ฆฌ: 32412KB / ์๊ฐ: 36ms
from itertools import combinations
N = int(input())
ret = []
for i in range(1, 11):
for j in combinations(range(9, -1, -1), i):
num = "".join(list(map(str, list(j))))
ret.append(int(num))
ret.sort()
if N >= len(ret):
print(-1)
else:
print(ret[N])
2. ๋ฐฑํธ๋ํน ์ฌ์ฉ
# ๋ฉ๋ชจ๋ฆฌ: 32412KB / ์๊ฐ: 40ms
N = int(input())
ret = []
def dfs(comb, last, length):
if len(comb) == length:
ret.append(int("".join(map(str, comb))))
return
for i in range(last-1, -1, -1):
comb.append(i)
dfs(comb, i, length)
comb.pop()
for length in range(1, 11):
dfs([], 10, length)
ret.sort()
print(ret[N] if N < len(ret) else -1)