9개의 댓글이 있습니다.

• 
  Jaekwan

  완전 탐색 방안도 잘 모르겠네요...흑

  
  9년 전 link

• 
  kriii

  분수들이 1/x 고 1<=x<=9니까 분모를 2520로 모두 통일시킵니다.
  그래서
  D[n,p] = n자리의 수이면서 분자의 합이 p인 수가 있다/없다. 라고 하면

  D[n,p] = D[n-1,p-2520] or D[n-1,p-1260] or ... or D[n-1,p-280]
  으로 점화식이 나오고 17자리까지 구해서 역추적은 적절히...

  
  9년 전 link

• 
  Jaekwan

  답변 감사합니다.
  2520이라는 숫자는 어디서 나온것이죠? 이해가 잘 안되네요..

  
  9년 전 link

• 
  Being

  1부터 9까지의 수의 최소공배수입니다.

  
  9년 전 link

• 
  Jaekwan

  그러면,
  p = 111111111111111111(최대수 17개의 1) 이곳에

  p = 2520^17 을 구한 후
  D[17, p] = D[n-1,p-2520] or D[n-1,p-1260] or ... or D[n-1,p-280] 을 재귀함수로 돌리는 건가요?
  점화식의 280의 숫자는 어떤 의미인가요?
  그리고 ..
  55555 = 0.2 + 0.2 + 0.2 + 0.2 + 0.2 = 1 의 케이스도 존재해서..

  
  9년 전 link

• 
  kriii

  소수로 생각하지마시고 분모가 2520인 분수로 생각하셔야 합니다. 그리고 280은 1/9 = 280/2520이라 나온겁니다

  
  9년 전 link

• 
  Being

  충분히 힌트를 드린 것 같으니 하루쯤 차분히 생각해보심이 어떨까요?

  
  9년 전 link

• 
  Jaekwan

  아직 역추적은 하지 않았구요.. 파이썬으로 작성 하였습니다.
  이런식으로 가게되면 트리의 레벨이 17단계나 내려가게 되네요.

  N = 17
  int_list = [2520, 1260, 630,504, 315] # 3,6,7,9 제외
  rep = 2520
  start = rep * N
  
  result = []
  def solve(n, p, li, result):
      if n < 1:
          return
  
      for i in li:
          new_p = p -i
          if new_p % rep == 0 :
              result.append(new_p/rep)
          solve(n-1, new_p, li, result)
  
  
  solve(N, start, int_list, result)
  

  
  9년 전 link

• 
  Jaekwan

  아이고, 제가 잘못 이해 했네요. 3,6,7,9도 포함 시켜야 하군요..

  
  9년 전 link

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