[백준 2355] 시그마

2355번: 시그마

시그마 공식을 활용하는 문제.

가우스 덧셈 공식, 시그마 (∑)

처음에는 반복문으로 풀었는데 너무 쉬워서 이상하다 했더니 런타임 에러가 발생했다.

• 시간제한에 걸리면 틀렸습니다 가 아닌 런타임 에러가 발생한다.

모르겠어서 검색을 했고 시그마 공식을 활용하는 문제였다.

(가우스 덧셈이라고 검색해도 나온다)

• 가우스 덧셈 공식
  • n < m 일 때, n부터 m까지의 정수를 모두 더한 값은
  • (n + m) * (m - n + 1) / 2
• 시그마 공식
  • n < m 일 때, n부터 m까지의 정수를 모두 더한 값은
  • 1부터 m까지의 합 - 1부터 n-1까지의 합과 같다 (1 + … + m) - (1 + … + n-1)
  • = [m(m + 1) / 2] - [n-1(n-1 + 1) / 2]
  • = [m(m + 1) / 2] - [n-1(n) / 2]
• 여기서 a와 b중 무엇이 더 큰지 모르므로, 대소비교를 한 다음 공식으로 적용한다.

풀이1 (시간초과)

let inputArr = readLine()!.split(separator: " ").map { Int($0)! }
print((inputArr[0]...inputArr[1]).reduce(0, +))

• for문으로 풀면 시간제한을 통과하지 못해 런타임 에러 발생

풀이2

• a와 b를 대소비교하여 각 경우에 다른 공식 적용

let inputArr = readLine()!.split(separator: " ").map { Int($0)! }
let a = inputArr[0]
let b = inputArr[1]
if a < b {
    print((b * (b + 1)) / 2 - (a * (a - 1)) / 2)
} else {
    print((a * (a + 1)) / 2 - (b * (b - 1)) / 2)
}

풀이3

• b가 반드시 a보다 큰 수가 되도록 보장한 뒤 하나의 공식 적용

let inputArr = readLine()!.split(separator: " ").map { Int($0)! }
let a = inputArr.min()!
let b = inputArr.max()!
print((b * (b + 1)) / 2 - (a * (a - 1)) / 2)