[골드 5] 백준 1419 - 등차수열의 합 (파이썬)

https://www.acmicpc.net/problem/1419

풀이

• 주어진 등차수열의 규칙은 다음과 같다.
  • k = 2: 수열은 3, 4, 5, ... 이므로 x ≥ 3
  • k = 3: 수열은 4, 7, 10, 13, ... → 일반항 3n + 1 → n ≥ 1
  • k = 4: 수열은 4, 6, 8, 10, 14, 16, ... → 짝수 중에서 12만 빠짐
  • k ≥ 5: 5n + 2 이고, n ≥ 2

각 케이스마다 상한 (r)까지 몇 개 있는지와 하한 (l)보다 작은 부분까지 몇 개 있는지를 구해서 그 차이를 구한다.

즉, f(r) - f(l - 1) 형태로 개수를 구한다.

각각 K = 2 ~ 4, K ≥ 5일때의 상황을 구해야한다.

1. k == 2 일때

if k == 2 :
    upper = max(0, r - 2)
    lower = max(0, l - 3)
    print(upper - lower)

항은 3부터 1씩 증가한다. 즉 개수는 r - 2, l - 3 부터 시작하며, r까지 r - 2개가 있다. l - 1 까지 l - 3 개가 있다.

1. k == 3 일때

elif k == 3 :
    upper = max(0, r // 3 - 1)
    lower = max(0, (l - 1) // 3 - 1)
    print(upper - lower)

• 항: 3n + 1 이므로 n ≥ 1부터 시작
• r // 3 - 1 → n의 최대값
• l - 1까지 있는 개수는 (l-1)//3 - 1

1. k == 4 일때

elif k == 4 :
    upper = max(0, r // 2 - 4)
    lower = max(0, (l - 1) // 2 - 4)

    if r >= 12 :
        upper -= 1
    if l - 1 >= 12 :
        lower -= 1
    print(upper - lower)

• 항: 짝수에서 12만 빠짐
• 기본적으로 짝수는 2n 형태이므로 r//2
• n ≥ 5부터 시작이므로 -4
• 다만 12는 제외되어야 하므로 r >= 12면 하나 줄이고, l - 1 >= 12면 하나 더 줄임

1. k ≥ 5 일때

else :
    upper = max(0, r // 5 - 2)
    lower = max(0, (l - 1) // 5 - 2)
    print(upper - lower)

• 항: 5n + 2이고 n ≥ 2
• r // 5 - 2 = 개수
• l-1까지에 해당하는 개수는 (l-1)//5 - 2

코드

# 백준 1419 - 등차수열의 합
# 분류 : 수학

l = int(input())
r = int(input())
k = int(input())

if k == 2 :
    upper = max(0, r - 2)
    lower = max(0, l - 3)
    print(upper - lower)
elif k == 3 :
    upper = max(0, r // 3 - 1)
    lower = max(0, (l - 1) // 3 - 1)
    print(upper - lower)
elif k == 4 :
    upper = max(0, r // 2 - 4)
    lower = max(0, (l - 1) // 2 - 4)

    if r >= 12 :
        upper -= 1
    if l - 1 >= 12 :
        lower -= 1
    print(upper - lower)
else :
    upper = max(0, r // 5 - 2)
    lower = max(0, (l - 1) // 5 - 2)
    print(upper - lower)