ryute   5년 전

그냥 다른 문제네요.

개구리 왕눈이는 N개의 연꽃잎이 있는 연못에 살고 있다. 연꽃잎은 1부터 N까지 차례대로 번호가 매겨져 있다. 연못을 위에서 보면 연꽃잎의 위치를 2차원 평면 위의 점으로 나타낼 수 있다. 왕눈이는 축에 평행한 직선으로만, 또 양의 방향으로만 뛸 수 있다. 따라서 왕눈이가 (x1,y1)에서 (x2,y2)로 뛰기 위해서는 아래 두 조건 중 하나를 만족해야 한다.

  • x2 > x1 이고 y2 = y1
  • y2 > y1 이고 x2 = x1

왕눈이가 한 번 뛰는데는 K만큼의 힘이 든다. 만약 왕눈이의 힘이 K보다 작다면 더 이상 뛸 수 없다. 왕눈이는 처음에 1번 연꽃잎에 있고, N번 연꽃잎으로 이동하려고 한다.  맨 처음에 왕눈이가 가진 힘은 0이다.

각 연꽃잎에는 파리가 산다. 왕눈이는 연꽃잎에 사는 파리를 먹을 수 있다. 1마리의 파리를 먹을 때 마다 왕눈이는 1의 힘을 회복한다. 처음에 왕눈이의 힘이 0이므로 왕눈이가 뛰기 위해서는 1번 연꽃잎에 사는 파리를 먹어 힘을 얻어야 한다는 점에 주의하자. 

당신은 왕눈이가 도착하고 난 뒤 가질 수 있는 힘의 최댓값을 구해야 한다. 더불어, 연꽃잎 사이를 이동하는 경로를 출력하는 프로그램 또한 작성해야 한다.

startlink   3년 전

수정했습니다.

kcm1700   2년 전

원래 번역은 모르지만 괜찮아보이네요. 문제 새로 읽는 분들은 혹시 힘이 든다는 표현이 헷갈린다면 "K만큼의 힘이 든다" -> "K만큼의 힘을 소모한다"로 이해하시면 될 것 같습니다.

댓글을 작성하려면 로그인해야 합니다.