[LeetCode/Medium] 2079. Watering Plants

1. Input

1) 각 식물들이 요구하는 물 양을 나열해둔 int 배열 plants

2) 내가 들고 다니는 물뿌리개의 용량 int 변수 capacity

3) 식물들의 위치는 0번째부터 시작

4) 물을 뜰 수 있는 강의 위치는 -1번째

 

2. Output

1) 모든 식물들에게 물을 주는 데 움직인 횟수 int 변수 moves

2) i번째에서 i+1번째로 움직이는 것은 1회 움직임으로 계산

3) 0번째부터 차례대로 물을 줘야 함

4) 식물이 요구하는 물을 줄 수 없을 경우 강까지 갔다가 다시 돌아와서 물을 줘야 함

  - 이때, 물뿌리개에 남은 물을 주고 강으로 가는 것은 허용되지 않음

  - 예를 들어, 1번째 위치에 있는 상황에서 2번째 식물에게 물을 줄 수 없다면 강으로 돌아갔다가(1 -> -1, 2회) 2번째에게 와서 물을 줘야 함(-1 -> 2, 3회)

5) 물을 미리 채우는 행동을 할 수 없음. 물의 양이 모자랄 때만 채우러 갈 수 있음

 

3. Constraint

1) n == plants.length

2) 1 <= n <= 1000

3) 1 <= plants[i] <= 106

4) max(plants[i]) <= capacity <= 109

 

4. Example

Input: plants = {2,2,3,3}, capacity = 5
Output: 14

설명: 물뿌리개에 5를 채우고 강(-1)에서 출발. moves = 0

  - i=0: plants[0]==2이므로 물을 줄 수 있음 -> i=0로 이동(moves += 1), 물뿌리개 == 3

  - i=1: plants[1]==2이므로 물을 줄 수 있음 -> i=1로 이동(moves += 1), 물뿌리개 == 1

  - i=2: plants[2]==3이므로 물을 줄 수 없음 -> 강으로 이동(moves += 2), 리필 -> i=2로 이동(moves += 3), 물뿌리개 == 2

  - i=3: plants[3]==3이므로 물을 줄 수 없음 -> 강으로 이동(moves += 3), 리필 -> i=2로 이동(moves += 4), 물뿌리개 == 2
  -> 최종 moves: 1+1+2+3+3+4 = 14

 

5. Code

1) 첫 코드(2022/08/18)

int moves = 0;
int can = capacity;
for(int i=0 ; i<plants.length ; i++){
    if(can>=plants[i]){
        can -= plants[i];
        moves++;
    }
    else{
        can = capacity;
        moves += 2*i;
        i--;
    }
}
return moves;

  - 물을 줄 수 있을 때만 한 칸 이동 가능

  - 물을 줄 수 없을 때는 강에 갔다가 원위치까지 하는 데의 왕복 횟수 = 편도 횟수 * 2