백준 1011번(Fly me to the...) 파이썬(python)으로 해결

 

특정한 거리를 몇 번의 횟수로 도달할 수 있는지 물어보는 문제입니다.

 

조건

 

처음 시작할 때와 마지막에 도착하기 전에는 반드시 1의 거리만 움직일 수 있다.

이전에 k만큼 움직였다면 이후에는 k-1, k, k+1의 범위에서만 움직일 수 있다.

 

---

접근 

 

먼저 표를 만들어 보고 어떤 규칙이 있는지 확인하였습니다.

 

문제가 제시한 조건

 

 

1~3의 거리는 특별한 규칙이 없어도 가능해서 버려두었습니다.

중요시 보아야 할 것은 제곱수의 거리(4, 9, 16)입니다.

 

 

제곱수를 기준으로 거리들을 나누었습니다.

(4, 5, 6, 7, 8), (9, 10, 11, 12, 13, 14, 15)

 

 

작동 횟수가 증가하는 구간은

거리가 5일 때 (횟수 = 4)

거리가 7일 때 (횟수 = 5)

거리가 10일 때 (횟수 = 6)

거리가 13일 때 (횟수 = 7) ...

 

 

 

이들이 가진 규칙을 풀어보게 되면

 

 

 

위와 같은 규칙으로 다음 값들을 유추해 보면

 

 

4*4+1(17)의 거리부터 작동 횟수는 4+4 = 8이며

4*5+1(21)의 거리부터 작동 횟수는 4+5 = 9입니다.

 

 

N의 값은 제곱수의 제곱근(4의 제곱근 = 2, 9의 제곱근 = 3)이며

M의 값은 N과 같거나 N보다 1 큰 수입니다.

 

 

제곱근과 이들의 규칙을 통해 횟수를 유추해 보겠습니다.

 

 

정수화한 제곱근을 N이라고 하고 (거리가 4이면 N = 2)

M의 값을 고정적으로 N+1이라고 했을 때 (M = 3)

정수 값이 같은 제곱근을 가지는 거리들(ex. 4, 5, 6, 7, 8)의 횟수는

 

 

거리가 N+N(4)이면 2N-1

거리가 N*N+1(5)와 같거나 큰 값이면 2N

거리가 N*M+1(7)과 같거나 큰 값이면 N+M = 2N+1

 

 

조건을 통해 각각의 경우에 맞는 공식을 적용시키면 문제를 해결할 수 있게 됩니다.

 

---

코드

 

거리가 1, 2, 3인 경우도 포함되어야 합니다.

1, 2, 3인 경우는 정수화된 제곱근이 모두 1입니다.

따라서 제곱근이 1이면 거리랑 같은 값이 횟수가 됩니다.

 

 

이후의 값들은 위의 계산식에 조건을 달아 작성하면 됩니다.

제곱근을 구하는 것은 math 모듈의 sqrt() 함수를 사용했습니다.

정수화 시키려면 제곱근 값에 int() 함수를 적용하면 됩니다.

 

 

1011 최종

 

 

 

 

 

-끝-