1841B - Keep It Beautiful

문제

https://codeforces.com/contest/1841/problem/B

Problem - B - Codeforces

풀이

값을 추가했을 때 배열이 beautiful 한 상태를 유지하려면, 아래의 조건이 만족해야 합니다.

• $a_i > a_{i+1}$ 인 경우가 반드시 $1$ 회 이하여야 합니다. 물론 $a_k > a_1$ 인 경우도 포함해서요. 

따라서, 우리는 이 문제를 두 가지로 나눌 수 있습니다. $a_i > a_{i+1}$ 인 경우가 아직 배열에 없는 경우, 그리고 이미 있는 경우로요. 조금 더 풀어서 설명드리자면, 배열에 내림차순인 값인 경우가 있는지의 여부를 의미합니다.

 

배열이 비어 있는 경우

이 경우 항상 새로운 수를 배열에 추가할 수 있습니다. 문제에서 값이 하나 있는 배열은 항상 beautiful 하다고 정의했으므로 가능합니다.

내림차순인 경우가 아직 배열에 없는 경우

만약 새롭게 추가될 수가 배열의 가장 마지막에 있는 수보다 크거나 같다면, 해당 수를 추가하는 것이 항상 가능합니다. 수를 추가한 뒤에도 배열은 항상 비내림차순 일테니까요.

그렇지 않다면, 새롭게 추가될 수와 배열의 첫 번째 수와 추가적인 비교를 해 보아야 합니다.

 

만약 새롭게 추가되는 수가 첫 번째 수보다 작거나 같다면, 이 경우에는 이전 수보다 작은 수가 새롭게 오더라도 beautiful 한 배열을 유지하는 것이 가능합니다. 비내림차순인 조건을 위배하는 경우가 생기지만, 새롭게 온 수를 시작점으로 본다면 이 위배하는 경우를 상쇄시킬 수 있기 때문에, beautiful 한 배열의 조건은 여전히 만족하도록 할 수 있습니다. 그 대신 앞으로 적는 수들은 무조건 내림차순으로 적을 수 없게 됩니다. 이번에 추가한 수를 시작점으로 잡아야지만 beautiful 한 배열이 성립되기에, 더 이상 이 방법으로 상쇄시키는 것이 불가능하기 때문입니다.

 

위의 배열에서 새로운 값으로 $1$ 을 추가하는 경우를 예로 들 수 있습니다. $1$ 을 추가하고, 시작점을 새롭게 추가한 수로 잡는다면 $[1, 2, 2, 4, 5]$ 가 되어 beautiful 한 배열의 조건을 만족시킬 수 있습니다.

 

만약 새롭게 추가되는 수보다 첫 번째 수보다 크다면, 이 값은 추가시키는 것이 불가능합니다. 이번에 추가한 수를 시작점으로 잡아야만 하는데, $a_k > a_1$ 인 경우가 생겨버리기 때문입니다.

 

이번에는 $3$ 을 추가하는 경우를 예로 들 수 있겠네요. $3$ 을 추가하고, 시작점을 새롭게 추가한 수로 잡는다면 $[3, 2, 2, 4, 5]$ 가 되어 beautiful 한 배열의 조건을 만족시키지 못 하게 됩니다.

 

내림차순인 경우가 배열에 이미 있는 경우

이 경우에는 시작점이 이미 정해진 이후이므로, 더 이상 내림차순인 경우가 나와서는 안 됩니다. 새롭게 추가되는 값이 내림차순을 이룬다면, 무조건 배열에 해당 값을 추가할 수 없습니다.

 

새롭게 추가되는 값이 내림차순을 이루지 않더라도, 첫 번째 값보다 큰 값이 추가될 경우 $a_k > a_1$ 인 경우가 생겨버리므로 역시 배열에 값을 추가할 수 없습니다.

 

요약하자면 새롭게 추가되는 값을 $a_k$ 라고 했을 때 $a_{k-1} \le a_k \le a_1$ 가 반드시 만족해야만 합니다.

 

틀렸던 이유

대회가 끝난 후에도 B번이 왜 틀렸는지 도저히 반례를 찾지 못 했는데, 댓글을 보다 이러한 반례를 찾아 제 코드의 문제점을 알 수 있었습니다.

내림차순인 경우가 배열에 아직 없는 상태일 때, 새로운 값이 추가되면 항상 값을 넣을 수 있다고 생각하고 무조건 1을 출력하도록 했는데, 위에서 설명드렸듯이 그럼에도 불가능한 경우가 있었는데 이를 캐치하지 못 한 것이 문제였습니다.

 

코드

https://codeforces.com/contest/1841/submission/209480497

Submission #209480497 - Codeforces

 

소감

요즘 좀 레이팅이 올라서 실력이 늘었다고 생각했는데, 크나큰 착각이었습니다.

버추얼(모의 대회 연습)을 많이 하지 않고, 업솔빙(대회가 끝나고 문제를 복습하는 것)을 소홀히 했기에 이렇게 되지 않았나 생각합니다. 그래서, 업솔빙을 꾸준히 하고자 블로그에 코드포스 풀이글을 쓰기로 했습니다.

좌절감이 크지만, 얼른 잊고 다음 대회를 위한 준비를 해야 겠습니다.