[백준 1024] 수열의 합

[ 백준 1024 : 수열의 합 ]

간만에 푼 백준~
쉬운 문제라고 생각하고 풀었는데 계속 틀려서 봤더니 예외 처리를 한 개 안해준것이 있었다.

만약 이 글을 보기전에 풀었을때 채점이 60%에서 자꾸 틀린다면 90%확률로 나와 같은 실수를 하셨을거라 생각한다.
바로 문제에서 말하는 "N과 L이 주어질 때, 합이 N이면서, 길이가 적어도 L이면서 가장 짧은 연속된 음이 아닌 정수 리스트를 구하는 프로그램을 작성하시오."
여기서 연속된 음이 아닌정수라 했으니 만약
3 3 이라는 입력이 주어지면
-1 이 나오는게 아니라
0 1 2 이렇게 나오는게 맞다.
이 예외때문에 60%에서 틀렸었고 이 예외만 고쳐주니까 맞았다.

그럼 어떻게 풀었는지 설명하겠다.

일단 이 공식을 무조건 알고 있어야한다.

등차수열의 합공식!!!!!

((수열의 길이) * (2*(수열의 첫번째 항)+(수열의 길이-1)*(등차))/2

지금부터 수열의 길이를 n 수열의 첫번째 항을 a 라고 하겠다. 연속된 수열이니 등차는 1이고 필요없는 수가된다.

수식을 다시 써보면
"(n(2a+n-1))/2 = N(=입력)" 가 된다.

풀어서 써보면
n^2 + (2a-1)n - N = 0
이러한 이차방정식이 나오고 우리가 알아야하는 a에 대해 식을 넘겨보면

(2a-1)n = N - n^2
2a-1 = (N - n^2)/n
a = ((N-n^2)/n + 1)/2

이렇게된다. a는 무조건 자연수라고 해보자 왜냐면 위에서 a가 0일때, 그러니까 0으로 시작할때는 미리 전처리로 구해놓고 시작하기 때문이다.
그럼 조건은 이렇게된다.
1. N-n^2 가 양수여야한다.
2. (N-n^2)는 n으로 나누어 떨어져야한다.
3. (N-n^2)/n + 1 은 2로 나누어 떨어져야한다.

이 세 조건을 만족해야한다.

그럼 for문으로 입력 L부터 탐색하면서 저 조건을 만족하는 a를 찾으면된다.

나는 처음에 풀 때 나올 수 있는 해(n의 값) 를 생각하면서 문제를 풀었었는데
n^2 + (2a-1)n - N = 0 이 이차방정식에서 나올 수 있는 n의 값은 무엇이 있을까? 일단 n은 무조건 자연수다.
그럼
N의 약수이면서 뺏을때 2a-1 이 나오는 수 중 더 작은 약수가 이차방정식의 해가된다.

그래서 N의 약수 중 L이상이면서 100이하인 수를 벡터에 집어넣었다.
그리고 그 벡터사이즈의 1/2 인덱스까지만 보면된다.
약수를 구하고 푼 소스.