사용자 도구

사이트 도구


ps:problems:boj:3152

예쁜 숫자

ps
링크acmicpc.net/…
출처BOJ
문제 번호3152
문제명예쁜 숫자
레벨실버 2
분류

애드혹

시간복잡도O(logn / logp)
인풋사이즈n<10^18
사용한 언어Python 3.11
제출기록31120KB / 40ms
최고기록40ms
해결날짜2024/01/23

풀이

  • 어떤 수가 트리 노드에 매겨진다는 것은, 그 수를 p진법으로 나타냈을때 0과 1만 존재한다는 것과 동치이다.
  • 이러한 수 두개를 더하게 되면, p가 3이상일때 p진법 상에서 받아올림은 일어나지 않고, 각 자리수에는 0,1,2 만 있게된다. n의 p진 표현의 각 자릿수 숫자들을 모은 배열을 L이라고 한다면, L에 0,1,2를 제외한 숫자가 있으면 n은 예쁜 숫자가 아니다.
  • 이 중에서, 0과 2는 각각 0+0, 1+1로만 만들어질 수 있기 때문에, 만약 L에 1이 없고, 0이나 2로만 이루어져 있다면 n을 두개의 수의 합으로 만드는 방법은 같은 수 두개를 더하는 방법뿐이 된다. 이는 다른 수 두개를 더해서 만들어야 한다는 조건에 위배되므로 예쁜 숫자가 아니다.
  • L에 1이 한 개 있다면, 이것은 다른 수 두 개를 더해서 만들수 있다. ??1? 이라는 수는 ??0? 와 ??1? 의 합으로 만들어질 수 있고, 이 외에는 다른 방법은 없다. 하지만, 1이 한개 있더라도, 1을 제외한 나머지 숫자가 모두 0이라면, 앞서 말한 것처럼 두수의 합으로 표현했을때 한쪽이 0이 되어서 트리 노드에 해당되지 않는 수가 된다. 그래서 이것까지 고려하면, L에 1이 한개 있고, 2도 한개 이상 있을때 n은 예쁜 숫자가 된다.
  • L에 1이 두 개 이상 있다면, n은 다른 수 두개를 더해서 만들어질수 있지만 그 방법이 여러가지가 있게 된다. 1?1? 이라는 수는 0?0? + 1?1? 또는 1?0? + 0?1? 의 두가지 방법으로 표현할수 있다. 다만 이번에도 한쪽이 0이 된다면 그렇게 나누는 방법은 불가능해지므로, 이것을 고려하면, L에 1이 2개 있고, 2가 한개도 없을 때 역시 n이 예쁜 숫자가 된다.
  • 정리하면 n이 예쁜 숫자가 되기 위한 조건은 다음과 같다.
    • L에 0~2만 있어야 하고,
    • (L.count(1) == 1 and L.count(2) > 0) 이거나 (L.count(1) == 2 and L.count(2) == 0) 이다
  • 시간복잡도는 n을 p진 표현으로 바꾸는데 필요한 O(log_p(n))이다

코드

"""Solution code for "BOJ 3152. 예쁜 숫자".

- Problem link: https://www.acmicpc.net/problem/3152
- Solution link: http://www.teferi.net/ps/problems/boj/3152

Tags: [ad hoc]
"""


def is_pretty(n, p):
    count = [0] * 3
    while n:
        n, m = divmod(n, p)
        if m > 2:
            return False
        count[m] += 1
    return (count[1] == 1 and count[2] > 0) or (count[1] == 2 and count[2] == 0)


def main():
    p, *n = [int(x) for x in input().split()]
    print(' '.join('1' if is_pretty(n_i, p) else '0' for n_i in n))


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
Q J X P L
 
ps/problems/boj/3152.txt · 마지막으로 수정됨: 2024/01/23 02:37 저자 teferi