시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 1024 MB | 270 | 122 | 97 | 57.059% |
햄최$125$인 지훈이는 먹은 햄버거를 소화하기 위해 $60$일을 굶었다. 슬슬 배가 고픈 지훈이는 부엌에서 직접 음식을 요리해 먹기로 했다.
부엌에는 인덕션이 있고, 인덕션에 요리할 수 있는 공간이 총 세 개 있다. 그리고 공간마다 따로 있는 온도 조절 버튼 $(-,+)$으로 온도를 조절할 수 있다. 온도는 다음 규칙을 따른다.
지훈이는 인덕션으로 $N$개의 음식을 순서대로 요리할 것이고, 각 음식을 요리하려면 정확한 온도가 필요하다. 즉, 세 개의 요리 공간 중 적어도 하나는 필요한 온도로 설정되어 있어야 음식을 요리할 수 있다. 음식을 요리하는 데 걸리는 시간은 무시한다.
배가 고파 힘이 없어진 지훈이는 모든 요리를 순서대로 완성하기 위해 온도 조절 버튼을 누르는 횟수가 최대한 적었으면 한다. 각 음식을 요리하기 위해 필요한 온도가 주어질 때, 모든 요리를 순서대로 완성하기 위해 온도 조절 버튼을 눌러야 하는 최소 횟수를 알려주자!
첫 번째 줄에 음식의 개수 $N$이 주어진다. $(1\leq N\leq 5\ 000)$
두 번째 줄에 각 음식을 요리하기 위해 필요한 온도를 나타내는 $N$개의 정수 $t_1,t_2,...,t_N$이 공백으로 구분되어 주어진다. $(0\leq t_i\leq 9)$
모든 요리를 순서대로 완성하기 위해 온도 조절 버튼을 눌러야 하는 최소 횟수를 출력한다.
1 5
5
2 3 9
4
5 9 3 8 1 0
7