시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1.5 초 (추가 시간 없음) | 1024 MB | 2338 | 795 | 608 | 40.185% |
$N$개의 카드가 놓여있다. 편의상 가장 왼쪽에 있는 카드를 $1$번 카드, 그 다음에 있는 카드를 $2$번 카드 $\dots$, 가장 오른쪽에 있는 카드가 $N$번 카드라고 하자.
$N$개의 카드에는 각각 정수가 하나씩 적혀있다. $i$번 카드에 적혀있는 수를 $x_i$라고 하자.
$N$개의 카드 중 일부에 적혀있는 수들을 적절히 바꾸어서, 왼쪽에서 오른쪽으로 갈수록 카드에 적혀있는 수들이 일정하게 증가하거나, 감소하거나, 또는 모든 수들이 같도록 하고 싶다.
카드에 적혀있는 수들을 바꿀 때는 정수 값으로만 바꿀 수 있으며, 바꾸는 횟수를 최소화해야 한다.
예를 들어, 아래의 그림과 같이 카드들이 주어졌다고 하자.
이 경우 $3$번 카드에 적혀있는 수를 $3$으로 바꾸면 아래와 같이 $1$씩 증가하도록 할 수 있고, 적혀있는 수를 바꾼 카드의 수는 $1$개이다.
다음과 같이 모든 카드에 적혀있는 수를 $2$가 되도록 할 수도 있다. 이때, 적혀있는 수를 바꾼 카드의 수는 $2$개이다.
가장 왼쪽에 있는 카드부터 가장 오른쪽에 있는 카드까지 각 카드에 적혀있는 수들이 순서대로 주어질 때, 조건을 만족하도록 하려면 바꿔야 할 카드 수의 최솟값을 구하여라.
첫 번째 줄에 카드의 수 $N$이 주어진다.
두 번째 줄에는 각 카드에 적힌 수 $x_i$가 공백을 사이에 두고 순서대로 주어진다.
첫 번째 줄에 답을 출력한다.
번호 | 배점 | 제한 |
---|---|---|
1 | 3 | $N ≤ 3$. |
2 | 10 | 답이 $2$ 이하이다. |
3 | 20 | 최소한의 카드들만 바꿔서 조건을 만족하게 했을 때, 인접한 카드에 적힌 수의 차가 $100$ 이하인 경우가 존재함이 보장된다. |
4 | 67 | 추가 제약 조건 없음. |
4 1 2 2 4
1
5 6 3 3 1 -1
2
Olympiad > 한국정보올림피아드 > KOI 2022 2차대회 > 초등부 2번
Olympiad > 한국정보올림피아드 > KOI 2022 2차대회 > 중등부 1번