Samsung DSA question

🪓 Problem: Logging Roadside Trees

The Korean Expressway Corporation is planning to expand the road where the volume of traffic is high. In order to expand the road, all the roadside trees nearby the road have to be chopped down.

To do this efficiently, they will rent a logging robot. However, the rental fee is high due to the high production cost, so we want to minimize the time taken by the robot.

🧠 The Logging Robot Has the Following Features:

1. The robot can move forward and backward.
   • Moving 1 unit takes 1 minute.
2. The roadside trees (left or right side) can be cut and loaded, which takes 1 minutes per tree.
3. Trees must be loaded in the order of their cut.
   • Only a tree whose length is shorter than or equal to the previously loaded tree can be loaded.
   • (i.e., non-increasing order of tree lengths)
4. If there are trees on both sides (left and right), without moving, each can be cut and loaded if the above order condition is satisfied.
5. The robot can load an infinite number of trees.

📐 Road Layout Description:

• The road is given as a straight line with a length of N.
• The first point (position 0) is the starting point.
• The last point (position N) is the ending point.
• On each side (left and right), there may be one tree at most at every unit length, with varying lengths.
• It is possible that there are no trees at a particular position.
• At the starting and ending points, there are no trees planted.

📋 Input Format:

1. The first line is an integer N — the length of the road.
2. The next two lines contain the lengths of the trees at each point from 0 to N:
   • First line: L — tree lengths on the left side.
   • Second line: R — tree lengths on the right side.
   • If there is no tree at a position, the length is given as 0.

🧾 Output Format:

Print the shortest time (in minutes) that is required to cut down all the trees, starting from the starting point to the ending point.

🧪 Example:

Example 1:

N = 5
L = 0 3 2 1 0 0
R = 0 3 2 1 0 0
Output: 11 minutes

Example 2:

N = 7
L = 0 5 1 5 9 1 5 0
R = 0 0 0 0 0 0 0 0
Output: 23 minutes

Example 3:

N = 10
L = 0 7 3 5 7 7 1 0 5 8 0
R = 0 7 7 0 1 0 1 1 0 0 0
Output: 51 minutes