풍선 터뜨리기

[sghong977]

마지막까지 남길 수 있는것 개수를 구하는 문제

접근법

1. n-1개 중 하나를 고름 (시작인덱스) -> 펑! (종류 2가지, 작은거 터뜨리는거 최대 한번)
2. 횟수 이미 썼는데 원소가 2개 넘는데 제일 작으면 그건 못터뜨리겠네
3. 큰게 항상 터지니까 큰걸 남기기 어려움
4. 큰 숫자 양옆에서 자기보다 작은애가 남는게 항상 가능하면? 절대 못남음. 양옆에 하나라도 큰 수가 남아줘야한다. (그래야 마지막 둘 중 하나로 작은애를 없애서 큰게 살아남음)
   -> 양옆에 숫자가 없거나 (배열 양끝) 자기보다 큰 수가 한쪽이라도 혼자서 살아남을수 있는지 확인하자.
   -> 한 방향씩.

아이디어 1

각 원소 기준으로 left, right에 최소값, 2nd 최소값을 저장함.

1. 최소값들과 비교해 셋중에 내가 제일 작다면 당연히 성공
2. 그런데 최소값 중 하나 없애고 2nd 최소값으로 대체하여 셋이 비교했을때에 내가 제일 작으면 성공
3. 최소값 계산은 중복이니까 누적해가며 풀자

잠만 쉬고 코딩해봐야지.

[sghong977]

답이 틀린다. 다른 경우가 있나 생각해보자.

시간초과는 안나지만 오답.
생각해보니까 first, second smallest 값을 저장하게 뒀지만 얘네끼리 붙어있으면 하나를 없앨 수 있어서, 좀더 큰 값까지 커버가 가능해서 아닌가 싶다. 내일 이어서 해보겠음.

fail1__balloon_boom.py 로 업로드 하겠음. 링크