[python] 숫자 블록

https://school.programmers.co.kr/learn/courses/30/lessons/12923

---

격자 형태로 그림을 그려서 -1 인덱스의 값을 리턴하면 되는 dp 문제라고 생각해서 테케1번을 dp 형식으로 풀어봤는데 답이 아니었다

def solution(begin, end):
    answer = []
    block = end // 2 + 1 # init 포함
    col = end - begin +1
    dp = [0 for _ in range(col)] 
    # dp[i][i*c] = max(dp[i-1][i*c], i)
    for b in range(1,block):
        for idx in range(2, col//b+1):
            dp[b*idx-1] = max(b, dp[b*idx-1] )
    
    return dp

 

인덱스의 약수에 해당하는 블록이 놓여진다는 건 알겠는데 소수를 판별하는 부분은 캐치하지 못해서 결국 풀이를 참고했다.

def solution(begin, end):
    answer = []
    for i in range(begin, end+1):
        if i == 1: # 1인 경우 0
            answer.append(0) 
        else:
            sqrt = int(i**0.5) # i의 제곱근
            for j in range(2, sqrt+1): # 에라토스테네스의 체
                q = i // j # 몫이 블록 수
                if q > 10**7: # 조건: 블록수 10**7개
                    continue 
                if i % j == 0: # 소수가 아닌 경우
                    answer.append(q) # 몫(블록)을 넣는다
                    break
            else:
                answer.append(1) # for문을 break 없이 돌았을 경우(= 소수인 경우) 1 추가
                    
    return answer