문제를 읽어보면 그냥 배수 찾고 공배수 중복제거하면 끝나네~라고 생각할 수 있다.
c, time = map(int, input().split())
stack=[]
for _ in range(c):
n = int(input())
for i in range(time//n):
num = n * (i+1)
if not num in stack:
stack.append(num)
print(len(stack))나도 그랬음.
그래서 바로 코드완료 했는데
시간초과에 걸렸다. 이중포문도 충분히 자원을 많이 잡아먹는데 이건 뺄 수 없고.. 게시판에 같은 케이스가 있어서 읽어보니 not num in 이 부분이 많이 잡아먹는다고 했다. 참고로 python3 대신 pyp3으로 하면 더 시간초과에서 넉넉할 거라고 해서 그렇게도 해본것임.
그래서 처음에는 set(O(1)연산)으로 해결하려고 리스트를 set으로 변경하여 중복제거를 하려고 했는데 이번엔
... 중복제거말고 플래그를 세워서 중복이 상관없게하는게 정답이었다.
아래는 시간초과를 해결한 최종본이다.
c, time = map(int, input().split())
stack=[0]*(time+1)
for _ in range(c):
n = int(input())
for i in range(n, time+1, n):
stack[i] = 1
print(sum(stack))
근데 이 마저도 python으로 하면 시간초과가 뜬다..
for문이 이중이라 특히 그런 듯 하다만, 하지만 이외의 방법이 생각나지 않는다.
공부