2965 : 캥거루 세마리 (Dynamic Programming) [C,C++]

내가 푼 방식이 DP가 아니라면 사실 이 문제는 DP로 풀지 않아도 되는 문제이다.

나는 이렇게 생각했다.

최대 몇 번 움직일 수 있을까?

최대로 움직이려면 간격을 한 번에 크게 좁히기보다 조금씩 좁히는 것이 낫다.

주어진 조건 정수에서 가장 조금씩 좁히는 방법은?

1씩 움직이자!

그래서 왼쪽 캥거루, 가운데 캥거루, 오른쪽 캥거루의 위치만 변경시키기로 했다.

조건 3가지만 이용하여 반복문을 돌렸다.

조건 1) 왼쪽 격차가 더 크다면 가운데 캥거루의 위치를 왼쪽 캥거루의 위치 + 1로 이동시키고 오른쪽 캥거루는 가운데 캥거루의 위치로 이동시킨다.

조건 2) 오른쪽 격차가 더 크다면 가운데 캥거루의 위치를 오른쪽 캥거루의 위치 - 1로 이동시키고 왼쪽 캥거루는 가운데 캥거루의 위치로 이동시킨다.

조건 3) 각 캥거루의 위치가 1씩 차이난다면 반복문을 탈출한다.

bool Kangaroo::Jump()
{
 if ((this->Center - this->Left) >(this->Right - this->Center))
 {
  this->Right = this->Center;
  this->Center = this->Left + 1;
  this->Count++;
 }
 else if (((this->Center - this->Left) == 1) && ((this->Right - this->Center) == 1))
 {
  return false;
 }
 else
 {
  this->Left = this->Center;
  this->Center = this->Right - 1;
  this->Count++;
 }
 return true;
}



<소스 코드>

*Source of the problem = https://www.acmicpc.net/problem/2965

*문제 출처 : BAEKJOON ONLINE JUDGE