[BOJ][B2]폭죽쇼- 1773

 

https://www.acmicpc.net/problem/1773

문제 전문은 링크 참조

문제가공

1. 각자 다른 등차를 가진 등차수열들의 합집합을 구한다.

코드작성

• 등차2 % 등차1 == 0 이면 등차1의 수열은 등차2의 수열의 모든 값을 가지기 때문에 계산할 필요가 없으므로 걸러낸다.
• 값을 구할때, 연산속도가 나눗셈(/,%) 보다는 곱셈(*)이 빠르므로 곱셈을 이용한다.

import sys
N,C = map(int, sys.stdin.readline().split())
interval = []
fireworks = {}
answer = 0 

for i in range(1, N + 1):
    interval.append(int(sys.stdin.readline()))

interval.sort()
for s_idx,i in enumerate(interval):
    if i== 0 : continue
    for e_idx in range(s_idx+1,len(interval)):
        v = interval[e_idx]
        if v ==0: continue
        if v % i == 0 :
            interval[e_idx] = 0
interval = list(filter(lambda x: x != 0, interval))
    
for inter in interval:
    i = 1
    while True:
        firework = i * inter
        if(i * inter > C):
            break
        fireworks[firework] = fireworks.get(firework,0)+1
        i+=1

print(len(fireworks))

개선된 풀이

문제를 통과하고 나서 다른 사용자들의 풀이를 보니,

입력된 시간(C)만 큼 배열에 공간을 확보하고

배열[폭죽] = 1 을 할당하여 1의 개수를 구하는 형태로 구현했고, 속도도 빨랐다.

리뷰

규칙성을 찾아내는데 한참 애먹었다.

예제(N = 2) 만 봤을 때는 각 수열의 리스트를 더하고, 최소공배수의 갯수를 제거하면 되나 싶었지만, 문제는 1≤N≤100이기 때문에

N ≥3 부터는 최소공배수들의 최소공배수도 계산해야햐고 재귀적으로 흘러가서 그냥 반복문을 때려 박았다.

메모리,시간제한 모두 간당간당하게 통과했다 (2초제한 / 1996ms)

.

.

.

어쨋든 통과했죠?