백준 1011. Fly me to the Alpha Centauri

tose33 2023. 7. 11. 14:39

https://www.acmicpc.net/problem/1011 1011번: Fly me to the Alpha Centauri 우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내

tose33.tistory.com

이전에 풀었던 문제를 다시 풀어봤는데 좀 이상해서 다시 기록.

이전에 푼 방식 백트래킹 방식은 지금보니 내 생각에 시간초과가 나야 정상인데 정답을 받았다.

1+2+3+...+n = (n *(N+1)) / 2 를 이용.

우선 최대 거리 만큼 이동해 본다.

예를들어 목적지가 13이라면

1 + 2 + 3 + 2 + 1 = 9

1 + 2 + 3 + 4 + 3 + 2 + 1 = 18

이므로 9만큼 우선 이동한다.

남은 거리는 4인데, 4를 중간에 이동할수는 없다. 그렇게 되면 규칙에 위반된다.

따라서 4를 여러개로 쪼개면 된다.

예를들어 4를 2+2 로 쪼개서

1+2+2+3+2+2+1 = 13

이런 식으로 만들면 된다.