[프로그래머스][C++] 짝수의 합
짝수의 합
문제 링크
분석
문제 그대로 n이하의 짝수를 모두 더한 값을 구하면 됩니다.
언더플로우나 오버플로우는 우려하지 않아도 됩니다.
for문과 if문을 사용해서 풀 수 있는 방법은 다음과 같습니다.
for 문으로 n까지 반복하며, if문을 사용해 현재 반복에서 짝수인지 홀수인지 확인하고, if문 안에서 항상 값을 더하거나 반복문을 넘어가면 됩니다.
for 문으로 n까지 반복하며, 초기화의 변수를 2에서 시작하며, 증감식은 이 초기화 식의 변수를 2씩 증가시키면 됩니다.
이 경우 초기화변수는 n에 2씩 가까워지며 항상 짝수를 유지합니다.
반복문 바디에서 항상 값을 더하고, 저장하면 됩니다.
등차수열을 이해하고 푸는 방법은 다음과 같습니다.
n이하의 모든 짝수이므로 첫 번째 항은 2로 시작하며, 마지막 항은 n(짝수) 혹은 n-1(홀수), 공차는 2인 등차수열입니다.
등차수열 합 공식은 첫 항과 마지막 항을 더한 뒤 항의 개수를 곱하고 2로 나눈 값입니다.
식으로는 다음과 같습니다.
하지만 위의 식은 짝수만을 더한 식은 아닙니다.
n이하의 모든 짝수를 더하는 등차수열 합에 대한 식은 다음과 같습니다.
이제 식을 찾았으므로 해당 문제를 식에 대입해서 사용하겠습니다.
풀이
for문으로 푸는 방법은 다음과 같습니다.
for문의 초기화 변수를 2씩 증가시키는 방법으로 풀겠습니다.
int solution(int n) {
int answer = 0;
for (int i = 2; i <= n; i += 2)
{
answer += i;
}
return answer;
}
for문의 규칙에 따라 for문에 사용되는 i 변수가 선언되며 값은 2로 초기화됩니다.
i가 n보다 작거나 같으면 반복문은 실행됩니다.
반복문이 실행되고 몸체의 코드가 실행되면 answer에 i가 더해집니다.
그 후 i는 2가 더해집니다.
예를 들면
n이 8일 때, i는 처음 2로 시작해 answer에 2가 저장됩니다.
그 다음 반복문에서 아직 i는 4로 n보다 작기 때문에 몸체의 코드가 실행되며 answer에 4가 더해져 6이 저장됩니다.
해당 반복이 i가 8일 경우까지 반복되고, i가 n보다 커지는 10이 됐을 경우 더해지지 않고 멈춥니다.
for 문의 자세한 설명은 아래 링크에 있습니다.
for문
등차수열을 이해하고 푸는 방법은 다음과 같습니다.
int solution(int n) {
int answer = (n / 2);
answer *= answer + 1;
return answer;
}
int answer = (n / 2)에서 짝수의 개수를 구합니다.
n이 5일 경우 2, 4로 2개며 12일 경우 2, 4, 6, 8, 10, 12로 6개입니다.
즉 n / 2를 하면 짝수의 개수가 나옵니다.
answer *= answer + 1는 다음과 같은 식에서 변형이 된 것입니다.
$k$는 짝수의 개수
$ S = \frac{k \times (2+ 2k)}{2} $
$ S = \frac{2k + 2k^2}{2} $
분자 $2k + 2k^2$를 분리
$ S = \frac{2k}{2} + \frac{2k^2}{2} $
$ S = k + k^2 $
이렇게 위의 과정을 거쳐 answer *= answer + 1가 됩니다.
성능 요약
for 문을 사용한 성능은 다음과 같습니다.
테스트 1 〉 통과 (0.01ms, 3.63MB) 테스트 2 〉 통과 (0.01ms, 4.08MB) 테스트 3 〉 통과 (0.01ms, 4.18MB) 테스트 4 〉 통과 (0.01ms, 4.16MB) 테스트 5 〉 통과 (0.01ms, 4.15MB) 테스트 6 〉 통과 (0.01ms, 3.68MB) 테스트 7 〉 통과 (0.01ms, 4.21MB)
등차수열의 합을 통한 성능은 다음과 같습니다.
테스트 1 〉 통과 (0.01ms, 4.21MB)
테스트 2 〉 통과 (0.01ms, 4.21MB)
테스트 3 〉 통과 (0.01ms, 4.2MB)
테스트 4 〉 통과 (0.01ms, 4.13MB)
테스트 5 〉 통과 (0.01ms, 3.63MB)
테스트 6 〉 통과 (0.01ms, 4.2MB)
테스트 7 〉 통과 (0.01ms, 3.66MB)
댓글남기기