2018년 2월 3일 토요일

[python][hackerrank] Utopian Tree

법칙을 찾는데 오래 걸렸다. easy인데 푸는데 너무 시간이 걸렸다. 리듀스 같은걸 쓰려고 고집해서 그런것 같기도 하다.
n res
0 1 = 1
1 1*2 = 2
2 1*2 + 1 = 3
3 (1*2 + 1) * 2 = 6
4 (1*2 + 1) * 2 + 1 = 7
5 14
6 15
7 30
8 31
even
2 3 2*1 + 1 -> 11
4 7 2*2 + 2*1 + 1 -> 111
6 15 2*2*2 + 2*2 + 2*1 + 1 -> 1111
8 31 2^4 2^3 2^2 2^1 +2^0 -> 11111
from functools import reduce

t = int(input().strip())

for _ in range(t):
    n = int(input().strip())
    print(reduce(lambda a,b: a+b, (map(lambda x: pow(2,x), range(((n+1)//2)+1)))) - n%2)

좀더설명하자면
n은
2일때 11
4일때 111
6일때 1111
8일때 11111
각각 1의 갯수만큼 이진수가 필요하다.
ex) n = 4
111 -> range(((4+1)// 2)+1) -> range(2+1) -> 1 2 3
저절로 1 2 3 이라고 나와주니 더 고맙다. 바로 pow를 이용해서 값을 구하자
[pow(2,1), pow(2,2), pow(2,3)]
그리고 다 더한다. reduce로
reduce(lambda a,b: a+b, [pow(2,1), pow(2,2), pow(2,3)])
그리고 even odd에 따른 차이를 뒤에 붙여준다.
 - n%2


댓글 없음 :

댓글 쓰기