19582. 200년간 폐관수련했더니 PS 최강자가 된 건에 대하여

거의 1달만에 푸는 문제라 쉬운 걸로 풀어봤다.

 

19582번: 200년간 폐관수련했더니 PS 최강자가 된 건에 대하여

---

 

$N$개의 대회가 주어진다. 지금까지 모은 상금이 $x[i]$원 이하라면 대회에 참여할 수 있고, $x[i]$원보다 많다면 대회에 참여할 수 없다. 이때 적어도 $N-1$개의 대회에 참여할 수 있는지 구하는 문제이다.

시간 초과 풀이

적어도 $N-1$개의 대회에 참여한다는 말은 $N-1$개 또는 $N$개의 대회에 참여한다는 말과 같다. 일단 $N$개의 대회에 모두 참여할 수 있는지 확인한 후, $N$개의 대회에 참여할 수 없다면 $N-1$개의 대회에 참여할 수는 있는지 확인하자. 

 

$i$번 대회에 참여하지 않았을 때 나머지 $N-1$개의 대회에 참여할 수 있는지 확인해 보자. $0$번 대회부터 대회를 선형 탐색하면서 $i$번 대회를 제외한 모든 대회에 참여할 수 있는지 확인하면 정답을 구할 수 있다.

 

당연하지만 이 풀이의 시간복잡도는 $O(N^{2})$이므로 시간 초과이다. 선형 시간에 해결할 수 있는 풀이를 찾아야 한다.

정답 풀이

적어도 $N-1$개의 대회에 참여한다는 말은 반대로 최대 하나의 대회를 건너뛸 수 있다는 말이다. 따라서 다음의 상태를 정의할 수 있다.

 

$dp[i][0]$: $i$번 대회까지 모든 대회를 참여했을 때 얻는 상금의 최솟값

$dp[i][1]$: $i$번 대회까지의 대회 중 대회 하나를 건너뛰었을 때 얻는 상금의 최솟값

 

$i$는 대회 인덱스, $j$는 건너뛴 대회의 수일 때 위의 식을 일반화하여 $dp[i][j]$로 나타낼 수 있다. $i$는 1씩 증가하니까 패스하고, $j$가 바뀌는 경로는 다음의 세 가지 경로뿐이다.

 

$0 \rightarrow 0$

$0 \rightarrow 1$

$1 \rightarrow 1$

 

$0 \rightarrow 0$과 $1 \rightarrow 1$ 경로는 $dp[i-1][f] \le x[i]$라는 조건을 만족해야만 갈 수 있다. 조건을 만족하지 못하면 $dp[i][f]$가 불가능함을 표시해야 한다. 나는 절대로 $dp$의 값이 될 수 없는 $2^{50}$을 할당하여 표시했다.

 

하지만 $0 \rightarrow 1$ 경로는 조건에 상관없이 무조건 갈 수 있다. 이제 위의 내용을 코드로 작성하면 된다.

맞왜틀

$p[i]$가 최대 $10^9$이고 $N$이 최대 $10^5$이므로 $dp$를 32비트 정수형으로 선언하면 오버플로우가 발생한다. 64비트 정수형으로 선언하자.

 

난 안 틀림 ㅎ

---