README.md

[Gold III] 인덕션 - 27925

문제 링크

성능 요약

메모리: 58620 KB, 시간: 480 ms

분류

다이나믹 프로그래밍

제출 일자

2024년 2월 19일 05:26:51

문제 설명

햄최125$125$인 지훈이는 먹은 햄버거를 소화하기 위해 60$60$일을 굶었다. 슬슬 배가 고픈 지훈이는 부엌에서 직접 음식을 요리해 먹기로 했다.

부엌에는 인덕션이 있고, 인덕션에 요리할 수 있는 공간이 총 세 개 있다. 그리고 공간마다 따로 있는 온도 조절 버튼 (−,+)$(-,+)$으로 온도를 조절할 수 있다. 온도는 다음 규칙을 따른다.

• 온도는 정수이며, 0$0$과 9$9$ 사이의 값이다.
• 처음에 모든 공간의 온도는 0$0$이다.
•  −$-$ / +$+$를 누르면 온도가 정확히 1$1$만큼 감소 / 증가한다.
• 온도가 0$0$인 상태에서 −$-$를 누르면 9$9$가 되고, 9$9$인 상태에서 +$+$를 누르면 0$0$이 된다.

지훈이는 인덕션으로 N$N$개의 음식을 순서대로 요리할 것이고, 각 음식을 요리하려면 정확한 온도가 필요하다. 즉, 세 개의 요리 공간 중 적어도 하나는 필요한 온도로 설정되어 있어야 음식을 요리할 수 있다. 음식을 요리하는 데 걸리는 시간은 무시한다.

배가 고파 힘이 없어진 지훈이는 모든 요리를 순서대로 완성하기 위해 온도 조절 버튼을 누르는 횟수가 최대한 적었으면 한다. 각 음식을 요리하기 위해 필요한 온도가 주어질 때, 모든 요리를 순서대로 완성하기 위해 온도 조절 버튼을 눌러야 하는 최소 횟수를 알려주자!

입력

첫 번째 줄에 음식의 개수 N$N$이 주어진다. (1≤N≤5 000)$(1\leq N\leq 5\ 000)$ 

두 번째 줄에 각 음식을 요리하기 위해 필요한 온도를 나타내는 N$N$개의 정수 t1,t2,...,tN$t_1,t_2,...,t_N$이 공백으로 구분되어 주어진다. (0≤ti≤9)$(0\leq t_i\leq 9)$ 

출력

모든 요리를 순서대로 완성하기 위해 온도 조절 버튼을 눌러야 하는 최소 횟수를 출력한다.