DP 문제로 보이네요.
1 3 5 2 7 3 5 6
위 상황을 풀어볼게요.
1 3 5 2 7 3 5 6
a b c d e f g h
a, b, c, d, e, f, g, h 자리에 하나씩 값을 채워볼건데, f 자리에는 (1, 3, 5, 2, 7, 3)만 있을 때 최대 점수, g 자리에는 (1, 3, 5, 2, 7, 3, 5)만 있을 때 최대 점수를 구해볼게요. 이렇게 이 위치까지만 있을 때의 점수를 그 수 아래에 적는겁니다.
우선 귀찮은 규칙인 맨 앞이랑 맨 뒤는 무조건 골라야 한다는 조건은 없다고 가정하고 풀어볼게요.
a 자리에 들어갈 값은 1만 존재할 때 최대 점수 => 1입니다.
b 자리에 들어갈 값은 1, 3만 존재할 때 최대 점수 => 4입니다.
c 자리에 들어갈 값은 1, 3, 5만 존재할 때 최대 점수 => 3이랑 5를 고르는게 최대겠죠. 8점입니다.
d 자리에 들어갈 값은 1, 3, 5, 2만 존재할 때 최대 점수 => 1 5 2를 고르거나 3 5를 고르는게 최선일것 같아요. 8점입니다.
이런식으로 채워나갈 수 있습니다.
초반 몇개는 채워봤으니 규칙을 볼게요.
1 3 5 2 7 3 5 6
1 4 8 8 e f g h
e를 채울겁니다. 1 3 5 2 7만 존재할 때 최대 점수네요.
우리는 맨 뒤 세개를 연속으로 고를 수 없습니다. 따라서 5 2 7 중 적어도 하나는 포기해야 할거에요.
7을 포기한다면 그 앞에 있는 1 3 5 2만 있을 때 최대한 점수를 높게 얻는 방법을 찾아야 합니다. 근데 그건 d와 같을테니 8점일겁니다.
2를 포기한다면 그 앞에 있는 1 3 5에서 최대한 점수를 얻고, 7은 무조건 고르는게 좋을거에요. 그럼 이건 c + 7 = 15점입니다.
5를 포기한다면 그 앞에 있는 1 3에서 최대한 점수를 얻고, 2랑 7은 무조건 고르는게 좋을거에요. 그럼 이건 b + 2 + 7 = 13점입니다.
셋중 제일 큰 15가 e겠네요.
1 3 5 2 7 3 5 6
1 4 8 8 15 f g h
같은 방식으로 f를 채워보면 f = max(e, d + 3, c + 7 + 3) = max(15, 11, 18) = 18일겁니다.
이런식으로 끝까지 채우면 맨 앞이랑 맨 뒤를 무조건 골라야 한다는 조건을 제외한 정답을 구할 수 있습니다.
맨 앞이랑 맨 뒤를 무조건 고르려면 => 세번째 값을 채울 때 1 3 5에서 3 5를 고르는게 제일 좋긴 하지만, 이러면 첫번째 값을 안 고르게 되니 차선책으로 1 5를 골라서 6점만 얻어서 c 자리에 6을 적습니다. 이러면 맨 앞을 안고르는 경우는 이 뒤에서 볼 일이 없습니다.
맨 뒤를 무조건 고르는건 마지막 값을 채울 때 h = max(g, f + 6, e + 5 + 6)을 할텐데, 그중 g는 맨 뒤를 안고른 경우니 빼버리고 h = max(f + 6, e + 5 + 6) 으로 구해줍시다.
DP 문제로 보이네요.
1 3 5 2 7 3 5 6
위 상황을 풀어볼게요.
1 3 5 2 7 3 5 6
a b c d e f g h
a, b, c, d, e, f, g, h 자리에 하나씩 값을 채워볼건데, f 자리에는 (1, 3, 5, 2, 7, 3)만 있을 때 최대 점수, g 자리에는 (1, 3, 5, 2, 7, 3, 5)만 있을 때 최대 점수를 구해볼게요. 이렇게 이 위치까지만 있을 때의 점수를 그 수 아래에 적는겁니다.
우선 귀찮은 규칙인 맨 앞이랑 맨 뒤는 무조건 골라야 한다는 조건은 없다고 가정하고 풀어볼게요.
a 자리에 들어갈 값은 1만 존재할 때 최대 점수 => 1입니다.
b 자리에 들어갈 값은 1, 3만 존재할 때 최대 점수 => 4입니다.
c 자리에 들어갈 값은 1, 3, 5만 존재할 때 최대 점수 => 3이랑 5를 고르는게 최대겠죠. 8점입니다.
d 자리에 들어갈 값은 1, 3, 5, 2만 존재할 때 최대 점수 => 1 5 2를 고르거나 3 5를 고르는게 최선일것 같아요. 8점입니다.
이런식으로 채워나갈 수 있습니다.
초반 몇개는 채워봤으니 규칙을 볼게요.
1 3 5 2 7 3 5 6
1 4 8 8 e f g h
e를 채울겁니다. 1 3 5 2 7만 존재할 때 최대 점수네요.
우리는 맨 뒤 세개를 연속으로 고를 수 없습니다. 따라서 5 2 7 중 적어도 하나는 포기해야 할거에요.
7을 포기한다면 그 앞에 있는 1 3 5 2만 있을 때 최대한 점수를 높게 얻는 방법을 찾아야 합니다. 근데 그건 d와 같을테니 8점일겁니다.
2를 포기한다면 그 앞에 있는 1 3 5에서 최대한 점수를 얻고, 7은 무조건 고르는게 좋을거에요. 그럼 이건 c + 7 = 15점입니다.
5를 포기한다면 그 앞에 있는 1 3에서 최대한 점수를 얻고, 2랑 7은 무조건 고르는게 좋을거에요. 그럼 이건 b + 2 + 7 = 13점입니다.
셋중 제일 큰 15가 e겠네요.
1 3 5 2 7 3 5 6
1 4 8 8 15 f g h
같은 방식으로 f를 채워보면 f = max(e, d + 3, c + 7 + 3) = max(15, 11, 18) = 18일겁니다.
이런식으로 끝까지 채우면 맨 앞이랑 맨 뒤를 무조건 골라야 한다는 조건을 제외한 정답을 구할 수 있습니다.
맨 앞이랑 맨 뒤를 무조건 고르려면 => 세번째 값을 채울 때 1 3 5에서 3 5를 고르는게 제일 좋긴 하지만, 이러면 첫번째 값을 안 고르게 되니 차선책으로 1 5를 골라서 6점만 얻어서 c 자리에 6을 적습니다. 이러면 맨 앞을 안고르는 경우는 이 뒤에서 볼 일이 없습니다.
맨 뒤를 무조건 고르는건 마지막 값을 채울 때 h = max(g, f + 6, e + 5 + 6)을 할텐데, 그중 g는 맨 뒤를 안고른 경우니 빼버리고 h = max(f + 6, e + 5 + 6) 으로 구해줍시다.