[문제 풀이 9] 코드 트리 - 연쇄로 터지는 폭탄

연쇄로 터지는 폭탄

 

• 문제 유형 : Simulation, Exhaustive Search
• 사용언어 : Python
• 난이도 : 실버 4
• 출처 : 코드 트리

 

https://www.codetree.ai/training-field/search/problems/series-of-bombs-detonating?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

n = int(input())
positions = [int(input()) for _ in range(n)]  # 폭탄의 위치
positions = sorted(positions)

offset = 10000
filed = [0]*offset

for i in range(n):
    filed[positions[i]] =1

# print(filed)
max_val = 0
for p in positions:
    # print("p : ", p)
    bomb = 1
    r_effect = 1
    start_p = p
    while True:
        box = []
        for i in range(start_p+1, start_p+r_effect+1, 1):
            if filed[i] == 1:
                box.append(i)
        r_effect +=1
        bomb +=len(box)
    
        if len(box)!=0:
            start_p = max(box)
        else:
            break
    
    l_effect =-1
    start_p = p
    while True:
        box = []
        for i in range(start_p-1, (start_p+l_effect)-1, -1):
            if filed[i] == 1:
                box.append(i)
        l_effect -=1
        bomb +=len(box)
    
        if len(box)!=0:
            start_p = min(box)
        else:
            break
    
    max_val = max(max_val, bomb)


print(max_val)