당신의 주유소에 있는 공기 펌프 줄이 너무 길어지고 있다! 당신은 손님들이 타이어, 스포츠 공, 거대한 퍼레이드 풍선 동물, 그 외 다양한 물건에 공기를 더 빨리 주입할 수 있도록 과정을 최적화하고 싶다.

이 펌프는 자동이다. 당신은 목표 압력을 특정 파스칼(pascal) 값으로 설정한 뒤, 펌프를 공기를 넣을 물건에 연결하면 그 정확한 압력까지 자동으로 공기를 주입한다. 펌프에는 버튼이 두 개뿐인데, 위(up) 버튼과 아래(down) 버튼이다. 각 버튼은 목표 압력을 정확히 1파스칼씩 올리거나 내린다.

Image of air pump and soccer ball.

손님이 \mathbf{N}명 줄을 서 있으며, 각 손님은 펌프로 공기를 넣어야 하는 물건을 정확히 \mathbf{P}개씩 가져온다. 당신은 각 물건의 목표 압력을 알고 있다. 당신은 한 손님이 가져온 물건들을 어떤 순서로든 처리할 수 있지만, 손님의 순서는 바꿀 수 없다. 즉 i번째 손님의 물건들을 모두 처리하기 전에는 (i+1)번째 손님의 어떤 물건도 처리할 수 없다. 두 물건을 연달아 처리할 때 목표 압력이 다르면, 펌프의 버튼을 눌러 목표 압력을 조정해야 한다.

펌프의 초기 목표 압력은 0파스칼이며, 모든 손님의 모든 물건을 처리한 뒤에는 어떤 값으로든 남겨도 된다. 각 손님에 대해 물건 처리 순서를 최적으로 선택한다면, 필요한 버튼 누름 횟수의 최소는 얼마인가?

#10430 upload 1 done 1 how_to_reg 1

Controlled Inflation timer 5s memory 1024MB

#10430

Controlled Inflation 5s 1024MB