💯Problem Solving
[BOJ] 28437 막대 만들기
date
Aug 9, 2023
slug
boj-28437
author
status
Public
tags
Python
BOJ
summary
백준 28437번 문제풀이입니다.
type
Post
thumbnail
category
💯Problem Solving
updatedAt
Aug 9, 2023 08:35 AM
문제 링크
문제
길고 얇은 막대를 만드는 과정은 다음과 같습니다.
- 기본으로 사용할 막대를 고릅니다. 사용할 막대의 길이는 A1, … An입니다.
- 원하는 길이가 될 때까지 0번 이상 막대를 늘립니다. 기계에 2이상의 양의 정수 k를 설정해서 막대를 넣으면, 길이가 x였던 막대가 길이 kx의 막대가 됩니다.
- 주어진 Q개의 길이 각각에 대해 길이가 L_i인 막대를 만드는 방법의 수를 출력하세요. 두 방법이 서로 다르다는 것은 처음 선택한 막대가 다르거나, 막대를 늘리는 과정에서 입력한 정수k의 수열이 서로 다르다는 것을 의미합니다.
문제풀이
Solved Arena #1 에 G번으로 출제되었던 문제다.
대회가 끝나고도 도저히 풀지 못해서 해답을 본 후 기록이다.
길이가 i인 막대를 만드는 방법의 수는 i인 막대를 그대로 사용하거나,
i의 약수인 막대를 k배 늘리는 것이다.
약수로 만들수 있는 막대의 bottom-up으로 구한후, 그 막대를 k배 하면 만들 수 있는 것이므로
막대를 사용하여 만든 작은 막대를 저장하고
약수에 해당하는 작은 막대를 모두 더해 큰 막대로 저장하면 된다.
인 v의 개수를 라고 하면,
로 점화식을 구할 수 있다.
파이썬 문제풀이 코드
import sys from itertools import count input =sys.stdin.readline N = int(input()) sticks = [0] * 100001 li = list(map(int, input().split())) M = int(input()) targets = list(map(int, input().split())) MX = max(max(li), max(targets)) dp = [0] * (MX+1) for a in li: dp[a] += 1 # ---------------------------------------------------------------------------------- # 약수를 구하고 그 약수로 늘린 막대의 갯수를 더해줌 # ---------------------------------------------------------------------------------- # for i in range(2, MX+1): # 최대값 까지 # for j in count(1): # if j * j > i: # j가 root i를 넘어간다면? , 약수가 될 수 없음 # break # if i % j == 0 : # j가 i의 약수라면 # dp[i] += dp[j] # j가 가지고 있는 값을 dp[i]에 넣어줌 # if j * j != i and j != 1: # 만약 j가 루트값이 아니고 1이 아니라면 # dp[i] += dp[i // j] # j로 나눠지는 값 ex) 6 = 2 * 3 (3)부분을 dp[i]에 넣어줌 # ---------------------------------------------------------------------------------- # 배수로 푸는 방법 i를 1부터 증가시켜주면서 i의 배수 j에 대하여 Dj에 Di를 더해주는 방향 # O(KlogK) # ---------------------------------------------------------------------------------- for i in range(1, MX+1): # 배수 base for j in range(2*i, MX+1, i): # 배수에 해당하는 값에 대하여 i로 늘린 막대의 갯수를 더해줌 dp[j] += dp[i] # Case # 5 # 1 2 3 4 5 # 6 # 1 2 3 4 5 6 # dp array init # 1 1 1 1 1 0 # 1 2 2 2 2 1 (i = 1) # 1 2 2 4 2 3 (i = 2) # 1 2 2 4 2 5 (i = 3) ANS # 1 2 2 4 2 5 (i = 4) # 1 2 3 4 2 5 (i = 5) # 1 2 3 4 2 5 (i = 6) print(*(dp[i] for i in targets))
시간복잡도
- 약수 :
- 배수 : 10x faster in large case
입력
출력
