조약돌 서브태스크
| 0.5 초 (추가 시간 없음) | 1024 MB | 1681 | 374 | 275 | 28.147% |
문제
좌우 한 줄로 있는 N개의 장소 각각에 조약돌이 몇 개씩 놓여 있다.
철수가 할 수 있는 작업의 종류는 아래 두 가지이다.
- 인접한 두 장소에서 임의의 동일한 개수의 조약돌을 가져가기
- 한 장소에서 임의의 개수의 조약돌을 가져가기
어떤 장소에 조약돌이 더 이상 없는 경우에도 그 장소는 그대로 남아 있어서, 초기에 인접하지 않았던 두 장소가 인접한 것으로 바뀌지 않는다.
철수는 위의 두 작업 중 하나를 골라서 실행하는 것을 반복하여 모든 조약돌을 가져가려고 한다.
초기에 각 장소에 있는 조약돌들의 개수를 입력받아, 철수가 할 수 있는 최소의 작업 횟수를 계산하는 프로그램을 작성하라.
입력
첫 번째 줄에 장소의 개수 N이 주어진다.
두 번째 줄에 N개의 장소 각각에 있는 조약돌 개수가 왼쪽 장소에 해당하는 것부터 순서대로 공백 하나씩을 사이로 두고 주어진다.
출력
첫 번째 줄에 답을 출력한다.
제한
- 2 ≤ N ≤ 2 500
- 각 장소의 초기 조약돌 개수는 1 이상 108 이하이다.
서브태스크
| 1 | 6 | N = 3. |
| 2 | 11 | N ≤ 15. |
| 3 | 19 | N ≤ 300. |
| 4 | 27 | 각 장소의 초기 조약돌 개수가 2 500 이하이다. |
| 5 | 37 | 추가 제약 조건 없음. |
예제 입력 1 복사
2
1 2
예제 출력 1 복사
2
예제 입력 2 복사
4
1 1 3 3
예제 출력 2 복사
2
예제 입력 3 복사
3
1 4 3
예제 출력 3 복사
2
예제 입력 4 복사
5
2 3 6 10 5
예제 출력 4 복사
4
해설
정답
/*
* Official Solution (C11)
* Gyojun Youn
* youngyojun [at] gmail [dot] com
*/
#include <stdio.h>
int B[2505][2505];
int A[2505], D[2505];
int N;
int main() {
//입력
scanf("%d", &N);
for(int i = 1; i <= N; i++)
scanf("%d", &A[i]);
//탐색
for(int i = 1; i <= N; i++) {
for(int j = i+1, x = A[i]; j <= N; j++) {
x = A[j] - x;
if(x < 0) break;
B[i][j] = !x;
}
}
//초기화
D[1] = 1;
//출력
for(int i = 2; i <= N; i++) {
int r = i;
for(int j = 1; j <= i; j++) {
int t = D[j-1] + (i-j) + !B[j][i];
if(t < r) r = t;
}
D[i] = r;
}
printf("%d\n", D[N]);
return 0;
}