백준 / 1773번 / 폭죽쇼 / Python / 수학,구현,브루트포스 알고리즘

📚문제

출처 : 백준 1773번 (https://www.acmicpc.net/problem/1773)

📝풀이

# 1773번 폭죽쇼(BronzeII)
import sys
n,c = map(int,input().split())
arr = [0]*(c+1)

for _ in range(n):
    t = int(sys.stdin.readline())
    for j in range(t,c+1,t):
        arr[j] = 1
print(sum(arr))

시간 초과가 관건인 문제⏳

이중 for문의 내부 for문에서

모든 수가 t의 배수인지( i %t==0) 판별하는 방식을 사용하면

시간초과에 걸리게 되서 

배열 생성 후 해당 인덱스의 숫자를 1로 변경해주는 풀이를 사용했다

 

그리고 이번엔 처음으로 시간초과가 아닌 메모리 초과 오류가 나기도하고

저 풀이로도 시간초과에 계속 걸려서 방법을 찾아봤다

PyPy3를 사용하여 제출하면 통과가 가능한 경우도 있다고 해서

PyPy3 언어로 제출하여 통과하였다

 

 

💡Python과 PyPy3의 차이

 

Python은 인터프리터(코드를 한 줄씩 읽어가며 실행/코드 수정 후 바로 실행 가능) 언어이다

 

PyPy3는 JIT(Just In Time) 컴파일 언어이다

* JIT 컴파일 : 프로그램을 실행하기 전 컴파일하는 대신, 프로그램 실행 시점에서 즉석으로 컴파일

                      주로 인터프리터 언어의 성능 향상 목적

PyPy3에선 자주 쓰이는 코드를 캐싱하는 기능

=> 인터프리터의 느린 실행속도 개선

=> 메모리를 조금 더 사용하여 코드를 저장하고 실행속도 개선

 

📌 간단한 코드 => Python3가 메모리 / 속도 측에서 우세

📌 복잡한 코드(반복) = > PyPy3 우세