Problem Check

요구 사항 정리

• 개의 나무가 원형 배열 형태로 존재하며, 매 벌목 과정 마다 만큼 자랍니다.
• 나무는  이상이 되면 벌목이 될 수 있고, 벌목된 나무의 높이만큼 구름이가 소지한 목재량이 늘어납니다.
• 구름이는 L, R, S 3개의 방법을 통해서 움직이고, 나무를 벌목합니다.
  • L은 왼쪽으로 한 칸, R은 오른쪽으로 한 칸, S는 현재 위치에서 멈춥니다.
• 모든 명령이 수행된 후, 구름이가 소지한 목재량을 구하면 됩니다.

알고리즘 정리

• 기본적으로 시뮬레이션을 하는 문제입니다. 하지만 의 풀이로는 풀리지 않기 때문에, 최적화가 필요한 문제입니다.
• 시간복잡도는 입니다.

Edge Case

• 어떤 나무도 벌목할 수 없 경우
• 인 경우

Problem Solving

주어진 개의 나무 높이를 관리하는 자료 구조와 개의 명령어를 관리하는 어떤 자료 구조나 변수를 선언합니다. 그리고 현재 명령어에 따른 구름이의 위치와 최종 목재의 개수를 관리하는 변수를 선언하여 시뮬레이션 문제를 풀기 위한 준비를 완료합니다. 명령어를 순회하면서 현재 위치의 나무 높이를 확인하고 벌목할 수 있으면 벌목을 진행합니다. 벌목 후에는 현재 위치의 나무 높이를 으로 설정합니다. L, R 명령어를 수행하고 나무의 높이를 씩 증가시키는 코드를 작성하면 간단하게 해결될 것처럼 보이지만, 이는 최적화가 필요한 시뮬레이션 문제이기 때문에 단순한 풀이는 틀렸습니다.

벌목 과정을 회 진행하면 모든 나무는 만큼 높아집니다. 따라서 진행된 벌목 과정의 횟수에 따라 나무 높이가 달라지므로 이를 반영하여 아래와 같은 수식을 만들 수 있습니다. 번째 나무의 초기 높이가 라면, 번째 벌목 과정에서 한번도 벌목되지 않은 번째 나무의 높이는 로 계산합니다. 번째 벌목 과정에서 번째 나무가 벌목되었다고 가정하면, 나무의 높이인 를 으로 초기화하는 대신에 만큼 뺍니다.