title: "[프로그래머스] 안티세포 Python 파이썬 해설 (Level 4) - 이도훈"
cleanUrl: "programmers/86054"
description: "프로그래머스 Level 4 문제 [안티세포]의 풀이를 정리합니다."

문제 설명 및 제한사항

아이디어 및 해결 방법

코드

import math
import bisect
MOD = int(1e9 + 7)

def binary_search(arr, x):
    idx = bisect.bisect_left(arr, x)
    
    if idx == 0 and arr[idx] != x:
        return -1
    elif idx == len(arr):
        return -1
    else:
        return idx

def solve(b):
    maxb, n = max(b), len(b)
    
    ps = [0, b[0]]
    for i in range(1, n):
        ps.append(ps[-1] + b[i])
    
    maxe = math.ceil(math.log2(ps[-1]))
    
    dp = [[0] * (maxe + 1) for _ in range(n)]
    dp[0][0] = 1
    
    for i in range(1, n):
        # e = 0인 기저 케이스들을 채웁니다.
        dp[i][0] = sum(dp[i-1])
        
        # 나머지 케이스들을 채웁니다.
        for e in range(1, maxe + 1):
            if dp[i][e-1] == 0:
                continue
            
            # jhalf를 찾습니다.
            target = ps[i + 1] - b[i] * 2**(e-1)
            jhalf = binary_search(ps, target)
            if jhalf == -1:
                continue
                
            eprime = math.log2(b[i] / b[jhalf - 1]) + (e - 1)
            if not eprime.is_integer() or eprime < 0:
                continue
            
            if not dp[jhalf - 1][int(eprime)] > 0:
                continue
            
            # jfull을 찾습니다.
            target = ps[i + 1] - b[i] * 2**e
            
            jfull = binary_search(ps, target)
            if jfull == -1:
                continue
            
            if jfull == 0:
                dp[i][e] = 1
            else:
            	dp[i][e] = sum(dp[jfull - 1]) % MOD
            
    return sum(dp[-1]) % MOD
    
def solution(a, s):
    answer = []
    
    start = 0
    for l in s:
        b = a[start:start+l]
        
        answer.append( solve(b) )
        
        start += l
        
    return answer

출처

프로그래머스 코딩테스트 연습 https://school.programmers.co.kr/learn/challenges