BadNeighbors

문제

모든 마을 사람들은 자신의 양 옆에 있는 이웃을 싫어합니다

마을은 우물을 기준으로 원형으로 구성되어 있으며
시계방향으로 돌며 우물수리를 위해
마을 사람 i 는 donations[i] 만큼 기부하려 합니다

이때 이웃이 기부를 하면 자신은 기부하지 않습니다

donations[] 의 시작과 끝은 서로 이웃이며
donations[] 는 2~40개의 요소를 갖고, 각 요소는 1~1000 사이의 값입니다

마을에서 얻을 수 있는 가장 큰 기부금액을 리턴한다

예시 입력

1)
10, 3, 2, 5, 7, 8

2)
11, 15

3)
7, 7, 7, 7, 7, 7, 7

4)
1, 2, 3, 4, 5, 1, 2, 3, 4, 5

5)
94, 40, 49, 65, 21, 21, 106, 80, 92, 81, 679, 4, 61, 6, 237, 12, 72, 74,
29, 95, 265, 35, 47, 1, 61, 397, 52, 72, 37, 51, 1, 81, 45, 435, 7, 36, 57, 86, 81, 72

예시 출력

19
15
21
16
2926

생각의 변화

10을 선택하면 다음은 2또는 5이다

이분탐색이 가능해 보인다

홀수개라면

dfs 는 이후 선택지를 들고있어야
select[] 를 인자로 받는다

선택정보도 전달해야 하므로
i 를 인자로 받는다

select[] 는 0으로 초기화 한다

dfs 종료조건은 i >= n 로 해서
select, donations 의 inner product 값을 리턴

i+2 와 i+3 을 선택

round 연산 필요

양옆을 체크하는 식

round 연산을 쓰면 dfs 종료조건으로 i >= n 은 부자연스러운듯 하다

select 가 잘못 들어간다면
if 에서 inner product 값을 리턴하면 안된다

dfs 종료조건은 제거
언젠가는 select 에 넣을수 있는 1이 다 되어, 양옆 체크조건을 충족불가하여
inner product 값이 리턴될 것

잘못 들어갈일이 없게 미리 select 로 양옆 체크하고, dfs 를 호출한다
이후, dfs 내에서 select[] 세팅

pseudo code

maxDonations(donations)
    n = donations.size()
    
    vector<int> select(n, 0)
    
    ret = 0
    
    for i=0  i<n  i++
        ret = max(ret, dfs(i, select, donations, n)
        
    return ret


dfs(i, select, donations, n)
    ret = inner_product(select.begin(), select.end(), donations.begin(), 0)
    
    if (select[i] == 1)
        return ret
        
    select[i] = 1
    
    res2 = 0, res3 = 0
    
    if (select[i+2-1 % n] == 0  &&  select[i+2+1 % n] == 0)
        res2 = dfs(i+2 % n, select, donations, n)
    
    if (select[i+3-1 % n] == 0  &&  select[i+3+1 % n] == 0)
        res3 = dfs(i+3 % n, select, donations, n)
        
    ret = max(ret, res2)
    ret = max(ret, res3)
    
    return ret

마지막 예제 시간초과

2초 시간조건을 고려해야 한다

생각의 변화

시간을 줄이려면 dp[] 를 메모해둬야 한다

메모해둘 내용은
dp[i] : i 까지 고려했을때 최대값

'i 까지 고려했을때' 문장이 성립하려면
원형으로 돌며 탐색하기 보다, 선형으로 탐색할수 있어야 한다
(구체적으로는, 다른 인접조건을 고려하는것 없이 0번 원소부터 탐색할수 있게)

선형으로 탐색할수 있게 경우를 나눈다

0번 원소를 선택한 경우

• [2..n-2]

0번 원소를 선택하지 않은 경우

• [1..n-1]

이렇게 2개의 선형탐색 구간이 나온다

이후 각 선형탐색 구간에 대해 다음의 점화식을 적용해본다

dp[i] 값을 메모할때
i번 원소를 선택한 경우

• dp[i-2] + num[i]

i번 원소를 선택하지 않은 경우

• dp[i-1]

두 경우중 큰 값이 dp[i] 가 된다

이후 dp[n-1] 을 리턴

pseudo code

maxDonations(donations)
    n = donations.size()
    
    if n == 1
        return donations[0]
        
     
    vector<int> case1(donations.begin(), donations.end() - 1)
    vector<int> case2(donations.begin() + 1, donations.end())
    
    return max(checkLinear(case1), checkLinear(case2))

checkLinear(numbers)
    n = numbers.size()
    
    if n == 1
        return numbers[0]
        
    vector<int> dp(n, 0)
    
    dp[0] = numbers[0]
    dp[1] = numbers[0] > numbers[1] ? numbers[0] : numbers[1]
    
    for i=2  i<n  i++
        dp[i] = max(dp[i-2] + num[i], dp[i-1])
        
    return dp[n-1]