WEIRD 문제 질문입니다.

  • aba1212
    aba1212
    1. 입력한 값의 약수들을 구한후 리스트에 추가했습니다.

    2. 그 리스트의 약수들의 모든 조합을 만들고 조합의 성분의 합을 입력 한 값과 비교해서 같다면 key라는 변수에 1을 넣고, key값을 이용해 바로 루프들을 빠져나오게끔 했습니다.

      ex) 12의 약수리스트[1,2,3,4,6]
      -> 조합 (1,2)(1,3)(1,4)(1,6).....(2,4,6)....(1,2,3,4,6)

      (2,4,6)에서 2+4+6=12이므로 key에 1넣고 루프 탈출해서 출력단계로

    3.key가 1이거나 약수들의 리스트안의 모든요소의 합이 입력값보다 작거나 같으면 "not weird"출력하고 이외의 경우에는 "weird"가 출력 되도록 했습니다.


    Problem => 값을 입력했을때 답은 잘 나옵니다만 시간초과라고 뜨네요. 위의 논리에서 어떤곳에서 시간을 줄여야할지 잘 모르겠어서 질문올립니다. 약수리스트에서 모든 조합을 구하고 그 합을 구하는 과정이 시간을 많이 잡아먹는거같은데 어떻게 수정해야할지...

    아래는 코드입니다. python3로 작성하였습니다.

    import sys
    import itertools as t
    rl = lambda: sys.stdin.readline()
    T = int(rl())

    for i in range(T):
    {

    w = int(rl().strip())
    li=[]
    key = 0
    for i in range(1,w):
    {
    if w%i==0 :
    li.append(i)
    }

    for i in range(2,len(li)+1):
    {
        a = map(sum, t.combinations(li, i))
    
        for i in a:
        {
            if i==w:
                key=1
                break
        }       
        if key==1:
            break
    }       
    
    if key==1 or sum(li)<=w:
        print('not weird')
    else:
        print('weird')

    }


    5달 전
0개의 댓글이 있습니다.
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.