프로그래머스 120831 - 짝수의 합 (Lv.0)

출처: https://school.programmers.co.kr/learn/courses/30/lessons/120831

// 프로그래머스 120831 - 짝수의 합 (Lv.0)
// https://school.programmers.co.kr/learn/courses/30/lessons/120831

// 문제 설명
// 정수 n이 주어질 때, n 이하의 짝수를 모두 더한 값을 반환하라.

// 제약 조건
// 0 < n <= 1000

// Example
// Input : n = 10
// Output: 30   (2 + 4 + 6 + 8 + 10)
//
// Input : n = 4
// Output: 6    (2 + 4)

// 접근 — 개수부터 세고 가우스 합으로 접기
// 더할 항을 나열하면 2, 4, 6, ..., 2k 형태의 등차수열이다. 루프로 훑어도 n <= 1000이라
// 통과하지만, 항의 "개수"만 알면 덧셈 자체를 없앨 수 있다.
// 1) n 이하 짝수의 개수 half = n / 2 (정수 나눗셈의 내림이 그대로 답 — n이 홀수여도 맞다).
//    n = 5면 half = 2, 짝수는 2와 4 두 개.
// 2) 합 = 2 + 4 + ... + 2*half = 2 * (1 + 2 + ... + half)
//           = 2 * half(half + 1) / 2 = half(half + 1).
// 3) 나눗셈 한 번, 곱셈 한 번으로 끝 — 반복문이 사라진다.
// 시간 O(1), 공간 O(1)

int solution(int n) {
    int half = n / 2;            // n 이하 짝수는 2, 4, ..., 2*half — 개수 = n/2 (내림)
    return half * (half + 1);    // 2*(1+2+...+half) = 2 * half(half+1)/2 = half(half+1)
}

정리

• “몇 개인지”를 먼저 세면 덧셈이 곱셈으로 바뀐다. 등차수열 합 문제의 공통 골격이다 — 항을 나열하지 말고 개수 half를 구한 뒤 가우스 합 half(half+1)/2에 공차 2를 곱한다. 여기서는 2를 곱하면서 /2가 상쇄돼 half(half+1)이라는 나눗셈 없는 식이 남는다.
• 내림 나눗셈이 홀짝 분기를 흡수한다. n / 2는 n이 홀수면 자동으로 마지막 홀수를 버리므로 if (n % 2) 같은 분기가 필요 없다. 정수 나눗셈의 내림을 “조건문 대신 쓰는” 패턴.
• 상한 점검: n = 1000일 때 half = 500 → 500 × 501 = 250,500. int로 여유롭다. 다만 이 식은 제약이 커지면 바로 넘친다 — n이 10억이면 half ≈ 5억, 곱은 약 2.5 × 10^17로 long long이 필수다. 곱셈 문제는 누적 상한부터 계산하고 자료형을 정하는 습관(12949 행렬의 곱셈에서 굳힌 것)이 여기서도 그대로 적용된다.
• O(n) 루프와 O(1) 식의 차이가 드러나는 지점은 제약이 커질 때다. n ≤ 1000이면 루프도 즉시 끝나지만, 같은 문제가 “n ≤ 10^18”로 나오면 루프는 애초에 불가능하고 식만 남는다. 제약이 작을 때 식으로 푸는 연습이 그 대비다.
• 검증: 예제 2개(30, 6)와 경계값 n = 1(→ 0)에 더해, 1부터 1000까지 전 구간을 루프 브루트포스와 대조해 전부 일치 (MSVC /std:c++17 /utf-8 컴파일·실행, n = 1000 → 250500).

핵심 요약 — 등차수열 합은 항을 나열하지 말고 개수부터 센다. half = n / 2의 내림이 홀짝 분기를 대신하고, 가우스 합에 공차 2를 곱하면 /2가 상쇄돼 half(half+1) 한 줄이 남는다.