백준 17088번 등차수열 변환

문제 링크입니다: https://www.acmicpc.net/problem/17088

17088번: 등차수열 변환

N의 크기가 최대 100,000이기 때문에 모든 경우의 수를 고려하는 코드를 작성할 경우 TLE가 발생할 것이 자명합니다.

따라서, 등차수열의 규칙을 생각해봐야 합니다.

수학에서, 등차수열은 연속하는 두 항의 차이가 모두 일정한 수열을 뜻합니다.

따라서, 등차수열이기 위해서는 (두 번째 숫자 - 첫 번째 숫자)의 차가 (세 번째 숫자 - 두 번째 숫자), (네 번째 숫자 - 세 번째 숫자), ..., (N 번째 숫자 - (N - 1) 번째 숫자)와 동일해야합니다.

즉, 두 번째 숫자와 첫 번째 숫자를 각각 독립적으로 [-1, 0, 1]한 결과를 토대로 등차수열을 유지할 수 있는지 연산해나가면 시간복잡도가 O(9 * N)이기 때문에 TLE 발생을 걱정하지 않아도 됩니다.

 

개발환경:Visual Studio 2017

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~