뚫기
시간 제한5초메모리 제한1024 MB
N개의 막이 있는 N×M 터널에서 순간이동 비용 A와 막 통과 비용 B가 주어질 때 최소 총비용을 구합니다.
문제
가까운 미래 싱가포르에서는 뚫기라는 게임이 유행 중이다. 게임 규칙은 간단하다. 쐐기 모양의 비행선이 크기의 터널을 왼쪽에서 오른쪽으로 통과하도록 움직이면 된다. 터널에는 비행선의 전진을 방해하는 초록색 막이 개 있다. 막은 각 칸의 왼쪽 벽에 위치하며, 여러 칸에 걸쳐 이어진 막은 하나의 막으로 본다. 편의상 비행선의 전진 방향을 축, 그에 수직인 방향을 축이라고 하면, 같은 좌표에는 막이 하나만 있다.
비행선은 각 칸에서 두 가지 움직임 중 하나를 할 수 있다. 첫 번째는 순간이동이다. 순간이동은 비행선을 현재 칸과 같은 좌표의 임의의 칸으로 옮긴다. 목적지가 어디든 비용은 항상 이다. 예를 들어 아래 그림은 에 있는 비행선이 로 순간이동하는 경우이며, 이때 비용 가 든다.
두 번째는 전진이다. 비용은 이다. 전진하려는 칸에 막이 있어도 비행선은 막을 뚫고 지나갈 수 있다. 이때는 비용 가 든다. 예를 들어 아래 그림은 에 있는 비행선이 로 전진하는 경우이다. 에 막이 있으므로 비용 가 든다.
비행선이 터널을 완전히 통과하면 게임이 끝나며, 게임 스코어는 통과하는 동안 발생한 비용의 합이다. 스코어가 낮을수록 좋다. 게임을 시작할 때 비행선의 좌표는 비용 없이 고를 수 있고, 게임이 끝날 때 좌표는 어디여도 된다.
터널 크기와 막의 위치가 같더라도 비용 와 가 바뀌면 최소 스코어와 그 스코어를 얻는 움직임이 달라질 수 있다. 주어진 터널과 막의 위치를 이용해 와 가 바뀔 때마다 가능한 가장 낮은 게임 스코어를 구하도록 다음 두 함수를 구현해야 한다.
void init( int N, int M, std::vector<int> Y1, std::vector<int> Y2 ) ;최초에 한 번만 호출된다.N과M은 터널의 크기 을 나타낸다.Y1과Y2는 길이가 인 배열이다. 부터 까지 막이 있다면Y1[X]는 ,Y2[X]는 이다.long long minimize( int A, int B ) ;A는 순간이동 한 번의 비용,B는 막을 한 번 뚫는 비용이다. 터널을 통과하는 데 필요한 비용의 최솟값을 구해 반환한다.