[C++] 백준 1011번 Fly me to the Alpha Centauri

처음 문제를 접근 했을 때

백트래킹으로 풀려고 시도했다. 재귀함수로 모든 경우를 돌면서 최소로 접근할 수 있는 것으로 계속해서 갱신하려고 했다. 구현은 했는데, 메모리 초과가 나면서 풀지 못했다.

모든 경우를 재귀로 돌면서 y-1보다만 작으면 이동할 수 있다고 생각한 풀이방법. 잘못된 풀이다.

 

단계별로 풀어보기에서 발견한 문제였는데, 분야가 수학이였다.

결국 조금 도움을 얻고자 게시판을 조금 검색해서 규칙성이 있다는 것을 얼핏 보았다.

잘 보면 규칙성이 있다.

그래서 이 규칙성을 가지고 어떻게 구현을 해야할까 고민했지만 결국 해답을 얻지 못했다.

글 읽기 - 풀이 정리해 보았습니다

그러다가 게시판을 찾던 중 이런 글을 발견했고, step마다 갈 수 있는 거리가 정해져 있다는 것이였다.

이동 횟수	과정	이동 거리
1	1	1
2	1 1	2
3	1 2 1	4
4	1 2 2 1	6
5	1 2 3 2 1	9
6	1 2 3 3 2 1	12
7	1 2 3 4 3 2 1	16

위 표를 보면 알 수 있듯,

이동 횟수가 짝수면 그냥 1 ~ 이동횟수/2 까지 모두 더한 값을 x2를 하면 이동거리가 되고

이동 횟수가 홀수면 그냥 1 ~ 이동횟수/2 까지 모두 더한 값에 x2 하고 이동횟수/2(소수점 버림) + 1을 하면 이동거리가 된다.

 

여기서 다 풀고 1 ~ n까지 합을 for 반복문으로 시도해서 시간 초과가 발생했다.

1 ~ n까지 합은 n(n+1)/2 로 구할 수 있는데 오래 안쓴 공식이다 보니 생각이 안났다.

사용한 STL과 변수

테스트 케이스를 받는 t와 시작점 x와 끝 점 y를 입력받았다.

 

이동횟수로 거리를 찾는 메서드

매개변수로 이동횟수를 받으면 이동가능한 거리를 알려준다.

1~n까지 합을 for반복문으로 구현했다가 시간초과가 났다...

1~n까지 합은 무조건 n(n+1)/2 이다!!!

 

메인함수

메인함수에서는 바깥 while 반복문으로 테스트 케이스만큼 돌리고

distance가 <= findDistanceByStep(이동횟수)가 되기 이전까지 반복문을 돌린다.

step을 1씩 증가시키면서 확인한다.

위에서 적힌 표에서 확인할 수 있듯이 step마다 움직일 수 있는 거리는 정해져 있다.

 

참고로 이동 거리 distance가 횟수로 찾은 이동거리보다 작거나 같으면 되는 이유는,

횟수로 찾은 이동거리보다 작거나 같은 distance는 결국 같은 횟수가 된다.

ex.)3은 1 1 1로 이동하므로 4와 같고, 5는 1 2 1 1로 이동하므로 6과 같다.

수학 관련된 알고리즘은 생각하기 항상 어려운 것 같다.

 

kimyunseok/study-record

코드는 위에서 확인 가능하다.