본문 바로가기
코딩과 알고리즘

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

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

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

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

 

2965번: 캥거루 세마리

문제 캥거루 세 마리가 사막에서 놀고 있다. 사막에는 수직선이 하나 있고, 캥거루는 서로 다른 한 좌표 위에 있다. 한 번 움직일 때, 바깥쪽의 두 캥거루 중 한 마리가 다른 두 캥거루 사이의 정수 좌표로 점프한다. 한 좌표 위에 있는 캥거루가 두 마리 이상일 수는 없다. 캥거루는 최대 몇 번 움직일 수 있을까? 입력 첫째 줄에 세 캥거루의 초기 위치 A, B, C가 주어진다. (0 < A < B < C < 100) 출력 캥거루가 최대 몇 번 움직일 수

www.acmicpc.net

막 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();
}