[Python] 백준1011 : Fly me to the Alpha Centauri

노가다 권씨 2024. 1. 7. 01:15

728x90

백준 알고리즘 골드5티어 문제입니다.

위치 x,y를 입력받아 간격 y-x를 규칙에 의해 이동하되 최소 도약횟수로 이동합니다. 이때 최소도약 횟수를 출력해주는 문제입니다. 규칙은 도약을 k만큼 할때 그 다음 도약에선 k-1,k,k+1만큼 도약을 할수있다는것, 처음과 마지막 도약은 1만큼 한다는것입니다.

최소도약횟수로 건너야하므로 한번 도약시에 규칙내에서 최대한 많이 도약하는게 필요합니다.

도약횟수가 바뀌는 임계점의 패턴을 알기위해 귀납법스러운 방식을 써봅시다.

표의 도약별 이동거리는 도약을 시각화(?)한겁니다. 예를들어 1 1 은 2번의 도약에서 각각 1,1만큼 이동한것이죠. 몇몇 간격값에선 도약별 이동값의 순서차이는 있을수있습니다. 예를들어 간격7에선 1 2 2 1 1이라고 써놔..야했지만 1 2 2 2 1로 오타가 났네요. 암튼 7은 1 2 2 1 1이 될수도, 1 2 1 2 1이 될수도 있죠. 거리별 도약의 경우의수를 따지는게 아니므로 크게 중요하지 않습니다. 중요한건 저 표에 의하면 간격에 7일때는 최소도약횟수가 5번이고 그 구성은 1 2 2 1 1 이라는것입니다. 여기서 또 주목할점은 도약 내 최댓값입니다. 한번 도약할때 최대로 이동하는 거리인데 예를들어 16의 경우 1 2 3 4 3 2 1 이므로 최댓값은 4이죠. '이전에 k만큼 도약했을경우 다음도약은 k-1, k, k+1만큼 할수있다'는 규칙과 '처음과 끝은 1만큼 도약한다'는 규칙때문에 도약은 약간 피라미드형으로 하게됩니다. 1부터 출발해 최댓값에 도달한후 다시 1로 돌아와야하므로 올라갔다 내려오는 개형이 발생하죠

여기서 주목해볼점은, 간격이 d일때 최댓값은 sqrt(d)의 정수부라는겁니다. 최댓값이 바뀌는 구간을보면 1, 4, 9, 16..으로 각 수의 제곱근만큼 최댓값을 갖습니다. 즉, 1-3까지는 최댓값이 sqrt(1), 4-8까지는 sqrt(4) 이런식으로요

출력해야하는것은 도약의 횟수입니다. 간격과 도약내 최댓값을 이용해 도약의 횟수를 정리할수있는데요, 아래는 다시 구간내 최댓값과 간격값, 갯수를 나타낸 표입니다.

이렇게 정리하니 좀 잘보이죠?

같은 최댓값을 갖는 도약에서 도약횟수가 변하는 간격(거리, y-x)의 수식적 특징입니다. 이건 사실 뭐 대단한방법을 써서 알아낸것은 아니고, 귀납법마냥 1부터 쭉써보다가 발견한 규칙입니다. 여러분도 한번 손으로써보시면 무슨말인지 아실겁니다. 저기서 간격은 임계점입니다. 해당 간격값까지가 해당 도약횟수를 갖는다는것이죠. 예를들어 y-x값이 4이면 2^2 임계점에 딱 걸려있으므로 도약횟수는 3입니다. 그러나 y-x가 5인경우 2^2를 초과하고 다음임계점 2^2+2 사이에 있으므로 도약횟수는 4입니다. 또한 친절하게도 도약내 최댓값이 m일때, 간격(y-x)의 임계점에 따라 도약횟수가 2m-1, 2m, 2m+1만큼

발생한다는것을 알수있습니다.

이제 다 끝났습니다. 코딩의 구조를 짜봅시다

테스트케이스와 x,y값을 입력받습니다. 간격은 y-x이고, 도약내 최댓값 k은 sqrt(y-x)의 정수부입니다.

최댓값 k에 대해 3단계의 임계점을 표현합니다. k^2, k^2+k, (k-1)xk+kx3 이 되겠네요.

그렇담 if문에 and조건으로 급간을 표현해 y-x값이 속하는 급간의 도약횟수값 2k-1, 2k, 2k+1중 하나를 출력해주면 됩니다.

test_case = int(input())

num_case=0

for i in range(test_case):
    x,y = map(int,input().split())

    dist = y-x
    k = int(dist**(1/2))
    
    if dist > k**2 and dist <= k**2+k:
        num_case = 2*k
    elif dist > k**2+k and dist <= (k-1)*k+k*3:
        num_case = 2*k+1
    elif dist <= k**2: 
        num_case = 2*k-1

    print(num_case)

원래 math라이브러리를 불러와 sqrt, trunc를 이용해 k값을 구하려했는데 알고리즘 문제나 코테에선 보통 외부 모듈을 사용하지 않는다네요...? 처음알았습니다 (코린이 이슈 ㅈㅅ;;)

이렇게 끝~~ 하면 좋겠지만 위에서 규칙에 대한 부연설명을 하기로했으니 해봅시다.

아마 간격 급간값에서 k^2 나 k^2+k까진 납득이 가실겁니다. 근데 문제는 2k+1의 도약횟수를 갖는 마지막급간 (k-1)xk+kx3이 살짝 컹스할겁니다. 특히 저 3이라는 숫자.. 뭘까...

위에서 말했듯 사실 이건 ~~필자의 미친 수학능력~~ 이 아닌 그저 노가다성 귀납법으로 알아낸건데요..

위 표에서 보시듯 저 구간의 특징이있습니다. 바로 최댓값이 바뀌기 직전의 상태 즉, 현재 최댓값으로 만들수있는 최대의 거리값이라는 겁니다. 그렇담 현재 최댓값으로 꽉꽉 채워야겠죠.

k값이 아무리 커져도 '3'이 유지되는 이유는, 1부터 k까지 (그림에선 h라고 표현되었네요) 도달하는데 소요되는 도약이 있고 또한 k부터 다시 1까지 도달하는데 도약횟수가 필요하므로, 그 상태에서 최댓값을 갖는 도약횟수가 3회가 나온겁니다.

(귀납법으로 구한거라 뭐라 설명하기가 힘드네요;;;; 님덜도 한번 숫자 쭉써보고 패턴 파악해보셈요)

문제를 풀며 과연 이렇게 손으로 숫자 패턴을 파악하면서 알고리즘 문제를 푸는게 맞나.... 컴푸터한테 계산을 맡겨야하는게 아닌가.. 라는 생각이 들었는데요... 근데 생각해보면 제가 기계공학을 전공하면서 귀에 딱지가 앉도록 들었던 말중에 하나가 "자동화와 인공지능을 구분하라"는 겁니다. (사실 귀에 딱지앉지는 않았고요, 자주 듣지도 않았습니다. 그냥 지난학기 인공지능 수업듣던중 한두번 들었지만 꽤나 인상적이었던말이라 한번 언급해봤읍니다...)

이런 알고리즘 문제는 자동화의 개념이므로 인간의 생각과 판단이 많이 들어가는게 맞지않나 싶습니다...

알고리즘을 체계화하는데 경우를 쭉 써보는 귀납법스러운 방식을 사용하는것도 구조화하는데 도움을 주는것같네요

(이거 풀고 다른분들 풀이봤는데 훨씬더 간단한 규칙을쓰심;; 사서 고생한듯요)