1011번 Fly me to the Alpha Centauri

1) 사이트

1011번: Fly me to the Alpha Centauri

 

 

 

2) 문제

보기만해도 읽기 싫었던 문제 ㅋㅋㅋ 이 문제 제가 간략히 설명해드리겠습니다 ^^

답정너 문제 해설!

 

출발지점 x -> 도착지점 y를 갈 때 몇 가지 규칙이 있습니다.

1 - 처음과 끝은 무조건 1회를 움직여야 한다.

2 - 만약 1회를 갔다면, 다음 턴을 0/1/2회 중 얼마나 갈지를 결정할 수 있다. (2회를 갔다면 1/2/3 회 중 결정이다.)

3 - 최소 이동 횟수를 구해야 한다.

 

예시를 들어볼까요?

만약 x = 0 / y = 2 일 경우, 처음 1번 / 마지막 1번으로 이동 횟수는 2번이 됩니다.

만약 x = 0 / y = 3 일 경우, 처음 1번 / 중간 1번 / 마지막 1번으로 이동 횟수는 3번이 됩니다.

계속 일정하게 늘어나냐? 오 절대 아닙니다! ㅎㅎ

만약 x = 0 / y = 4 일 경우, 처음 1번 / 중간 2번 / 마지막 1번으로 이동 횟수는 3번이 됩니다.

 

에엥~? 그럼 대체 어떤 규칙을 가지고 있을까요?

 

x	y(y-x)	횟수
0	1 (1^2)	1
0	2	2
0	3 (제곱수 사이 중간 값)	3
0	4 (2^2)	3
0	5	4
0	6	4
0	7 (제곱수 사이 중간 값)	5
0	8	5
0	9 (3^2)	5
0	10	6

10개까지 계산해놓고, 규칙을 찾아보았습니다.

일단 첫 번째로 알 수 있는 것은 제곱 수 바로 다음 수는 이동 횟수에 변동이 있다는 것을 알 수 있었습니다. [ex. y=(y-x)=2 / 5 / 10]

그리고 두 번째로 알 수 있었던 것은 제곱 수와 제곱 수 사이 특히 중간 값에 변동이 있다는 것을 알 수 있었습니다.

 

그렇다면 변동 횟수는 어떻게 구해질까요?

제가 집중한 부분은 중간 값 이전과 이후의 이동 횟수 입니다.

 

예로 4(2^2)와 9(3^3)를 분석해볼게요.

위의 표를 보시면 4와 9 사이 중간 값은 7 입니다. (9-4)/2 = 2.5 -> 9-2.5 = 6.5 -> 반올림 = 7 즉, 7이 중간 값 입니다.

7 이전은 4를 7 이후는 5의 이동 거리를 가지는 것을 확인할 수 있습니다.

 

이 이동 거리를 계산하는 방법은 아래와 같습니다.

(제곱 수와 제곱 수 사이 값들은 가장 큰 제곱 수를 이용합니다. 즉 4와 9 중에선 9를 이용합니다.)

7 이후 값은 루트(9)x2-1

7 이전 값은 루트(9)x2-2

 

손으로 써가며 알아낸 방법입니다... (인증샷 찰칵)

 

 

 

3) 파이썬 코드

import math
test_case=int(input()) #테스트 케이스
x=0 #출발지점
y=0 #끝지점
y_x=0 #y-x
zg=1 #제곱 범위 찾는데 쓰인다.
result=0 #결과값

for i in range(0,test_case):
    x,y=input().split()
    y_x=int(y)-int(x)
    
    #1부터 돌며 제곱수 범위 찾기 1~4(2제곱)/ 4~9(3제곱) 
    while(1):
        if(y_x<=zg**2):
            #범위를 찾았다. -> 중간 값인지 알아보기 / 중간 값 이상이면 *2-1이다.
            if(math.ceil(zg**2-((zg**2-(zg-1)**2)/2))<=y_x):
                result=zg*2-1
                x=0
                y=0
                y_x=0
                zg=1
                break
            
            #범위를 찾았다. -> 중간 값 보다 작으면 *2-2이다.
            else:
                result=zg*2-2
                x=0
                y=0
                y_x=0
                zg=1
                break
            
        
        else:
            #다음 범위를 찾는다.
            zg=zg+1
        
    print(result)

위의 설명을 그대로 코드로 적용하면 위와 같습니다.

 

3-1) 선수 지식

파이썬 코드를 이해하기 위해 알아야 할 선수 지식이 있습니다.

 

1. 올림, 내림, 반올림

import math

#올림
math.ceil(숫자)

#내림
math.floor(숫자)

#반올림 내장 함수 아님
rount(숫자)

참고 사이트 :

[Python] 파이썬 - 05. 올림(ceil), 내림(floor), 반올림(round)

 

3-2) 설명

 

1. 사용할 변수를 선언 및 초기화 해줍니다.

test_case=int(input()) #테스트 케이스
x=0 #출발지점
y=0 #끝지점
y_x=0 #y-x
zg=1 #제곱 범위 찾는데 쓰인다.
result=0 #결과값

 

2. 테스트 케이스를 몇 회 돌린 것인지 받고, 각 케이스마다 출발 지점 (x), 도착 지점 (y)을 받은 후 y-x를 계산합니다.

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

 

3. 제곱 수의 범위를 찾습니다. 만약 y-x=7일 경우 다른 제곱 수 1과 4를 지나쳐 9의 범위로 인식합니다.

#1부터 돌며 제곱수 범위 찾기 1~4(2제곱)/ 4~9(3제곱) 
    while(1):
    	#범위 내에 들어간다.
        if(y_x<=zg**2):
            
        
        else:
            #범위가 아닐 경우 다음 범위를 찾는다.
            zg=zg+1

 

4. 범위를 찾았을 경우 중간 값을 구하고 그 이상의 값인지 이하의 값인지 찾는다.

while(1):
        if(y_x<=zg**2):
            #범위를 찾았다. -> 중간 값인지 알아보기 / 중간 값 이상이면 *2-1이다.
            if(math.ceil(zg**2-((zg**2-(zg-1)**2)/2))<=y_x):
                result=zg*2-1
                x=0
                y=0
                y_x=0
                zg=1
                break
            
            #범위를 찾았다. -> 중간 값 보다 작으면 *2-2이다.
            else:
                result=zg*2-2
                x=0
                y=0
                y_x=0
                zg=1
                break
            
        
        else:
            #다음 범위를 찾는다.
            zg=zg+1

중간 이상이면 루트(범위의 제곱수)x2-1 그보다 작으면 루트(범위의 제곱수)x2-2로 계산한다.

무한 루프를 돌렸기 때문에 계산 후 변수 초기화 및 break을 써 제어해준다.

 

5. 결과를 출력한다.

print(result)

 

4) c언어

없음

 

---

궁금한 점이나 공유할 정보가 있다면 댓글로 남겨주세요 *^^*

끝!