글 읽기 - 한쪽은 시간초과 한쪽은 메모리초과......

jinwoolee0366 2년 전 0

처음은 소인수 2의 개수와 소인수 5의 개수를 구하는 방식으로 시도했지만 시간초과가 나왔습니다.

몇 가지 변형으로 시도해도 결국 큰 틀의 변화가 없어 통과하지 못했습니다.

그다음 dp 방식으로 풀려고 시도한 결과 시도하자마자 메모리 초과......

고수님들 제에발 도와주세요ㅠㅠ

# 일반적인 방식
n, m = map(int, input().split())

cnt_2 = 0
cnt_5 = 0

for i in range(1, n+1):
    a = b = i # i 를 보존하고 a, b 로 while 을 돌리기
    while a % 2 == 0:
        cnt_2 += 1
        if i <= m: # 보존된 i로 판단
            cnt_2 -= 1
        if i <= n-m:
            cnt_2 -= 1
        a = a // 2
    while b % 5 == 0:
        cnt_5 += 1
        if i <= m:
            cnt_5 -= 1
        if i <= n-m:
            cnt_5 -= 1
        b = b // 5
        
print(min(cnt_2, cnt_5))

# dp 방식
import sys
n, m = map(int, sys.stdin.readline().split())

mem = [0 for _ in range(n+1)]
for i in range(1, n+1):
    if i % 2 == 0:
        mem[i] = mem[i//2] + 1
n_2 = sum(mem[:n+1]) # 1~n까지의 소인수 2의 총 개수
m_2 = sum(mem[:m+1])
nm_2 = sum(mem[:n-m+1]) # nm == n-m
tot_2 = n_2 - (m_2 + nm_2)

mem = [0 for _ in range(n+1)] # 메모리 리셋
for i in range(1, n+1):
    if i % 5 == 0:
        mem[i] = mem[i//5] + 1
n_5 = sum(mem[:n+1])
m_5 = sum(mem[:m+1])
nm_5 = sum(mem[:n-m+1])
tot_5 = n_5 - (m_5 + nm_5)

print(min(tot_2, tot_5))

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

한쪽은 시간초과 한쪽은 메모리초과......

jinwoolee0366 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말