Where who wants to meet someone
백준 Swift [24265] 알고리즘 수업 - 알고리즘의 수행 시간 4 본문
난이도
브론즈 III
문제
https://www.acmicpc.net/problem/24265
24265번: 알고리즘 수업 - 알고리즘의 수행 시간 4
오늘도 서준이는 알고리즘의 수행시간 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. 입력의 크기 n이 주어지면 MenOfPassion 알고리즘 수행 시
www.acmicpc.net
내 답안
import Foundation
let input = Double(readLine()!)!
print(Int((pow(input, 2) - input) / 2))
print(2)n = 7
1: 2 to 7 -> 6
2: 3 to 7 -> 5
3: 4 to 7 -> 4
4: 5 to 7 -> 3
5: 6 to 7 -> 2
6: 7 to 7 -> 1
수행 횟수: 21 = 6 + 5 + 4 + 3 + 2 + 1
여기까지 봤을 때 n-1부터 n까지 더한다는 것만 생각이 나서 전체 규칙을 발견하고자 하나하나 '물리'적 풀이를 했다.
n = 2
1: 2 to 2 -> 1
수행 횟수: 1 = 1
n = 3
1: 2 to 3 -> 2
2: 3 to 3 -> 1
수행 횟수: 3 = 2 + 1
n = 4
1: 2 to 4 -> 3
2: 3 to 4 -> 2
3: 4 to 4 -> 1
수행 횟수: 6 = 3 + 2 + 1
n = 5
1: 2 to 5 -> 4
2: 3 to 5 -> 3
3: 4 to 5 -> 2
4: 5 to 5 -> 1
수행 횟수: 10 = 4 + 3 + 2 + 1
2는 1 // 3은 3 // 4는 6 // 5는 10 // 7은 21
n/2 2n/2 3n/2 4n/2 6n/2
n/2 (n-1)n/2 (n-1)n/2
(n-1)n/2
n^2-n / 2
위와 같은 단계를 거쳐 n^2-n / 2 라는 결론이 나오게 되었다.
'백준 알고리즘 문제 기록 > 시간 복잡도' 카테고리의 다른 글
| 백준 Swift [24267] 알고리즘 수업 - 알고리즘의 수행 시간 6 (0) | 2023.07.03 |
|---|---|
| 백준 Swift [24266] 알고리즘 수업 - 알고리즘의 수행 시간 5 (0) | 2023.07.03 |
| 백준 Swift [24264] 알고리즘 수업 - 알고리즘의 수행 시간 3 (0) | 2023.07.03 |
| 백준 Swift [24263] 알고리즘 수업 - 알고리즘의 수행 시간 2 (0) | 2023.07.03 |
| 백준 Swift [24262] 알고리즘 수업 - 알고리즘의 수행 시간 1 (0) | 2023.07.02 |
