백준 1011번 문제풀이 - Fly me to the Alpha Centauri

백준 1011번 문제

 

 

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

1011번: Fly me to the Alpha Centauri

 

처음에 문제를 풀 때 문제 이해를 잘못해서 2시간 정도를 허비했다. 틀렸다고 떠서 문제를 처음부터 다시 읽어보니 잘못 이해하고 풀었다는 것을 알았다.

 

이 문제는 패턴이 잘 보이지 않아서 다른 블로그 선생님의 설명을 보고 노트에 표를 만들어보며 이해했다. 

대략적인 패턴은

출발과 끝 사이 거리 (y - x) 1, 2, 4, 6, 9, 12, 16, 20 ,25, 30

                                     1  2  2  3  3   4   4   5   5

이런 식으로 수가 커지는 것을 볼 수 있다.

이러한 패턴을 4, 9, 16, 25 제곱수를 눈여겨보고 제곱근을 활용하여 패턴을 찾았다

횟수가 3에 위치한 4의 값과 횟수 5에 위치한 9의 값을 보면 거리의 제곱근의 2배 - 1의 값을 가지는 것을 볼 수 있고

횟수가 4에 위치한 5의 값과 횟수 6에 위치한 10의 값을 보면 거리의 제곱근의 2배의 값을 가진다.

횟수가 5에 위치한 7의 값과 횟수 7에 위치한 15의 값을 보면 거리의 제곱근의 2배 + 1의 값을 가진다.

 

이러한 패턴은 제곱수가 되는 수 사이의 값을 보며 나뉘어 지는데

이때의 식을 만들어서 3가지 경우로 출력하게 했다.

 

 

 

 

 

코딩

1.

문제를 이해하고 나만의 방식으로 풀었을 때인데 상당히 지저분한 것을 볼 수 있다. 경우의 수를 깔끔하게 나누지 못했던 것이 크다.

 

 

 

2.

다른 분은 어떻게 풀었는지 구글링 해보고 깔끔하게 정리된 것을 보고 다시 풀었다.

 

 

 

 

 

결과

1.

 

2.

 

약간의 속도 차이가 있는 것으로 보인다.

 

 

 

 

 

느낀 점

문제를 잘못 이해해서 오래 걸린것도 있지만 수학적인 사고를 잘 해야만 했다. 문제의 패턴을 찾는데 오랜 시간이 걸렸고 경우의 수를 만들어가는 것도 복잡하게 느껴졌다. 맞았다고 출력이 됐지만 자주 보고 있는 자바문제풀이 블로그 선생님의 글을 보고 다시 한 번 제대로 이해할 수 있었고 깔끔한 코딩을 할 수 있었다. 검색하면 항상 상단에 노출되시는 것으로 보아 온라인 제자를 많이 두신것 같다.

 

 

 

 

 

 

참고 : https://st-lab.tistory.com/79

[백준] 1011번 : Fly me to the Alpha Centauri - JAVA [자바]