백준 2965번. 캥거루 세마리 해설, 소스

오늘 또 백준 문제 풀이 러쉬를 해서 오랜만에 또 백준 문제를 하나 다뤄볼텐데요 :)

캥거루 3마리가 서로 다른 정수의 좌표에 있는데 바깥쪽에 있는 캥거루가 다른 2마리 캥거루 사이의 빈 정수 지점에 점프한다고 칠 때 최대 몇번까지 움직일 수 있는 지는 구하는 문제입니다.

​

https://www.acmicpc.net/problem/2965

2965번: 캥거루 세마리

막 2분 탐색이 어떻고 생각하면 매우 어려워지는 문제이지만

사실 이 문제는 매우 쉬운 문제입니다.

최단횟수가 아닌 최장횟수를 구하는 문제이기 때문이지요 :)

​

캥거루 3마리가 3 5 9 좌표에 있다고 칠 때,

캥거루가 가장 많이 움직일 수 있는 방법은

맨 처음에는 3~5와 5~9중 넓은 쪽에 뛰어드는 것입니다.

뛰어들긴 뛰어드는데, 7이 아닌 6으로 뛰어드는 것입니다. ( 8로 뛰어들어도 되긴 합니다 )

​

만일 7 위치로 뛰어들면 5 7 9가 되어 다음에 1번밖에 못 뛰어들지만

5 6 9가 된다면 5가 7로 뛰어들 수 있고

6 7 9 에서 6이 8지점으로 뛰어들 수 있기 때문이지요.

한마디로 1칸씩 야금야금 전진하면서 뛰어들면 최장횟수만큼 뛸 수 있습니다.

​

숫자폭이 너무 작아서 잘 이해가 안되신다면,

한가지 예를 더 들어보겠습니다.

100 200 250 지점에 캥거루가 있다면,

100 ~ 200 쪽이 200~ 250보다 더 공간이 넓으므로 250캥거루가 101 지점으로 점프,

100 101 200 에서 100 캥거루가 102로 점프.

101 102 200 에서 101 캥거루가 103으로 점프,

이렇게 큰 공간으로 뛰어든 다음, 한칸씩 점점 파고드는 것이지요.

​

사실 이 과정을 시뮬레이션할 필요는 없습니다.

정답은 "넓은 공간의 캥거루의 간격 - 1"만큼이 점프횟수가 됩니다.

​

캥거루가 10 11 12 와 같이 모두 다닥 붙어있는 경우인 경우도 문제없이 구해지더라구요 :)

아주 간단한 소스 공개합니다.

 

#include <iostream>
#include <cstring>
#include <cmath>

void Result()
{
	int a, b, c;
	scanf("%d %d %d", &a, &b, &c);
	int len1 = b-a;
	int len2 = c-b;
	int len3;
	if(len1>len2)len3=len1;
	else len3=len2;
	printf("%d", len3-1);
}

int main()
{
    Result();
	getchar(); getchar();
}