0 또는 1의 값을 가지는 n개의 요소로 이루어진 배열 A가 있다고 가정해 보겠습니다. 여기에 나무가 하나 있고, 연속된 n일 동안 A[i]가 0이면 물을 주지 않고, 1이면 물을 줍니다. 나무는 다음과 같은 규칙에 따라 성장합니다.
- 이틀 연속으로 물을 주지 않으면 나무는 죽습니다.
- i번째 날에 물을 주면 1cm 자랍니다.
- i번째 날과 (i+1)번째 날에 연속으로 물을 주면 1cm 대신 5cm 자랍니다.
- i번째 날에 물을 주지 않으면 그날은 자라지 않습니다.
나무의 초기 높이는 1cm입니다. 우리의 목표는 n일 후 나무의 최종 높이를 구하는 것이며, 만약 나무가 중간에 죽었다면 -1을 반환해야 합니다.
예시 이해하기
입력이 A = [0, 1, 1]이라고 해보겠습니다. 이 경우 출력은 7이 됩니다.
- 첫째 날: 물을 주지 않았으므로 자라지 않습니다. 높이는 1cm입니다.
- 둘째 날: 물을 주었지만 전날(첫째 날)에는 물을 주지 않았으므로 1cm 자랍니다. 높이는 2cm입니다.
- 셋째 날: 어제(둘째 날)와 오늘 모두 물을 주었으므로 5cm 자랍니다. 높이는 2 + 5 = 7cm입니다.
문제 해결 접근 방법
이 문제는 배열을 한 번만 순회하면서 전날의 물 주기 상태를 기억하는 방식으로 해결할 수 있습니다. 핵심 로직은 다음과 같습니다.
- 현재 높이(r)를 1로, 전날 물 준 여부(y)를 0으로 초기화합니다.
- 오늘(x)과 어제(y) 모두 물을 주었다면 높이를 5 증가시킵니다.
- 오늘만 물을 주었다면 높이를 1 증가시킵니다.
- 어제와 오늘 모두 물을 주지 않았고, 이미 하루 이상 경과했다면(i > 0) 나무가 죽었으므로 r을 -1로 설정합니다.
- r이 이미 -1이라면 이후 반복에서 아무 작업도 수행하지 않고 건너뜁니다.
r := 1 y := 0 n := size of A for initialize i := 0, when i < n, update (increase i by 1), do: x := A[i] if r is same as -1, then: Ignore following part, skip to the next iteration if x is non-zero and y is non-zero, then: r := r + 5 otherwise when x is non-zero, then: (increase r by 1) otherwise when not x is non-zero and not y is non-zero and i > 0, then: r := -1 y := x return r
C++ 구현 코드
아래 구현 예제를 통해 더 자세히 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
int solve(vector<int> A){
int r = 1;
int y = 0;
int n = A.size();
for (int i = 0; i < n; ++i){
int x = A[i];
if (r == -1)
continue;
if (x && y)
r += 5;
else if (x)
++r;
else if (!x && !y && i > 0)
r = -1;
y = x;
}
return r;
}
int main(){
vector<int> A = { 0, 1, 1 };
cout << solve(A) << endl;
}입력
{ 0, 1, 1 }출력
7
복잡도 분석
이 알고리즘은 배열을 한 번만 순회하므로 시간 복잡도는 O(n)이며, 추가 메모리를 거의 사용하지 않아 공간 복잡도는 O(1)입니다. 매우 효율적인 선형 탐색 방식의 시뮬레이션 문제 해결 예시라고 할 수 있습니다.