2회 문제풀이 15 / ABC 116 C - Grand Garden
ABC C - Grand Garden
【문제 개요】
화단에 N개의 꽃이 피어있으면 각각 1, 2, …, N라고 번호가 부여되어 있습니다.
최초 모든 꽃의 높이는 0입니다. 수열 h = {h1, h2, h3, …}를 입력받습니다. 다음의 물주기행동를 반복하는 것으로 모든 k(1 ≦ k ≦ N)에 대해서 꽃 k의 높이를 hk로 만들려고 합니다.
- 물주기 : 정수 l, r를 지정한다. l ≦ x ≦ r를 만족하는 모든 x에 대해서 꽃 x의 높이를 1 높힙니다. 조건을 만족하기 위해 최소 물주기 행동을 몇번 해야할까요?
힌트 : 깊이 우선 탐색(DFS) 알고리즘
【전제】
- 1 ≦ N ≦ 100
- 0 ≦ hi ≦ 100
- 입력받을 모든 수는 정수이다.
【입력 형태】
1
2
N
h1 h2 h3 ... hN
【출력 형태】
조건을 만족하기 위한 최소 물주기 행동 횟수를 출력하시오.
【예시】
입력 예 1
1
2
4
1 2 2 1
출력 예 1
1
2
물주기행동을 이하와 같이 하면 2번이 최소가 됩니다.
- (l, r) = (1, 3)으로 물주기 행동을 합니다. (1, 1, 1, 0)
- (l, r) = (2, 4)으로 물주기 행동을 합니다. (1, 2, 2, 1)
입력 예 2
1
2
5
3 1 2 3 1
출력 예 2
1
5
입력 예 3
1
2
8
4 23 75 0 23 96 50 100
출력 예 3
1
221
ABC C - Grand Garden
【문제 개요】
화단에 N개의 꽃이 피어있으면 각각 1, 2, …, N라고 번호가 부여되어 있습니다.
최초 모든 꽃의 높이는 0입니다. 수열 h = {h1, h2, h3, …}를 입력받습니다. 다음의 물주기행동를 반복하는 것으로 모든 k(1 ≦ k ≦ N)에 대해서 꽃 k의 높이를 hk로 만들려고 합니다.
- 물주기 : 정수 l, r를 지정한다. l ≦ x ≦ r를 만족하는 모든 x에 대해서 꽃 x의 높이를 1 높힙니다. 조건을 만족하기 위해 최소 물주기 행동을 몇번 해야할까요?
힌트 : 깊이 우선 탐색(DFS) 알고리즘
【전제】
- 1 ≦ N ≦ 100
- 0 ≦ hi ≦ 100
- 입력받을 모든 수는 정수이다.
【입력 형태】
1
2
N
h1 h2 h3 ... hN
【출력 형태】
조건을 만족하기 위한 최소 물주기 행동 횟수를 출력하시오.
【예시】
입력 예 1
1
2
4
1 2 2 1
출력 예 1
1
2
물주기행동을 이하와 같이 하면 2번이 최소가 됩니다.
- (l, r) = (1, 3)으로 물주기 행동을 합니다. (1, 1, 1, 0)
- (l, r) = (2, 4)으로 물주기 행동을 합니다. (1, 2, 2, 1)
입력 예 2
1
2
5
3 1 2 3 1
출력 예 2
1
5
입력 예 3
1
2
8
4 23 75 0 23 96 50 100
출력 예 3
1
221
このポストは作成者の CC BY 4.0 ライセンスによって保護されます。