Codeforces Round 260 (Div. 1) - Boredom 링크
(2023.08.16 기준 Difficulty *1500)

문제

수열 a가 주어진다. 수열 a의 원소 a_k를 하나 골라서 삭제하면 점수 a_k를 얻고, 수열의 모든 a_k-1과 a_k+1인 원소가 삭제된다. 최대로 얻을 수 있는 점수 출력

알고리즘

DP

풀이

언뜻 보면 정말 쉬운 dp지만, 문제를 잘 읽어야 한다.
연속된 인덱스를 선택이 불가능한 것이 아니라 연속된 수를 선택이 불가능한 것이다.

예를 들어, 수열에서 5를 골랐다면? 수열의 모든 4와 6이 없어지는 것이다. 여기서 잠깐, 그렇다면 수열에 남은 5들은? 당연히 선택이 가능하다.

결국은, 수열의 수들이 나온 횟수를 구해준 다음에, 우리가 많이 봐온 연속된 인덱스를 선택이 불가능한 문제를 나온 횟수로 하여금 풀면 된다.

코드

• C++

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAX = 100000;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n; cin >> n;
    int a[n]; for (int i = 0; i < n; i++) cin >> a[i];

    // 각 수가 나온 횟수를 저장
    int ct[MAX + 1]; memset(ct, 0, sizeof(ct));
    for (int i = 0; i < n; i++) ct[a[i]]++;

    // 연속되는 수를 선택하지 못한다.
    // 직전 수를 선택하지 않거나 현재 수를 선택하지 않는 두 경우가 최선의 경우이다.
    ll dp[MAX + 1]; memset(dp, 0, sizeof(dp));
    dp[1] = ct[1];
    for (int i = 2; i <= MAX; i++) dp[i] = max(dp[i - 2] + (ll)ct[i] * i, dp[i - 1]);

    cout << dp[MAX];
}

• Python

import sys; input = sys.stdin.readline

n = int(input())
a = list(map(int, input().split()))

# 각 수가 나온 횟수를 저장
ct = [0] * 100001
for i in range(n):
    ct[a[i]] += 1

# 연속되는 수를 선택하지 못한다.
# 직전 수를 선택하지 않거나 현재 수를 선택하지 않는 두 경우가 최선의 경우이다.
dp = [0] * 100001
dp[1] = ct[1]
for i in range(2, 100001):
    dp[i] = max(dp[i - 2] + ct[i] * i, dp[i - 1])

print(dp[100000])