백준 1011. Fly me to the Alpha Centauri

https://tose33.tistory.com/536

백준 1011. Fly me to the Alpha Centauri

 

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

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

 

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 

 

이런 식으로 만들면 된다.