Where who wants to meet someone
백준 Swift [24267] 알고리즘 수업 - 알고리즘의 수행 시간 6 본문
난이도
브론즈 II
문제
https://www.acmicpc.net/problem/24267
24267번: 알고리즘 수업 - 알고리즘의 수행 시간 6
오늘도 서준이는 알고리즘의 수행시간 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. 입력의 크기 n이 주어지면 MenOfPassion 알고리즘 수행 시
www.acmicpc.net
내 답안
let input = Int(readLine()!)!
print((input - 2) * (input - 1) * input / 6)
print(3)중첩 for문에서 횟수를 어떻게 세어야 하는지 제대로 파악하지 못해서 처음에 두 번 실패했다.. n^2 - 2n인줄 알았다.
도저히 답이 안나와서 다시 한 번 경우의 수를 세본 결과 다음과 같았다.
n = 7
1번 for문: 1 to 5 -> 5번
2번 for문
2 to 6 -> 5번
3 to 6 -> 4번
4 to 6 -> 3번
5 to 6 -> 2번
6 to 6 -> 1번
3번 for문
5 + 4 + 3 + 2 + 1번
4 + 3 + 2 + 1번
3 + 2 + 1번
2 + 1번
1번
수행 횟수 35 = 15 + 10 + 6 + 3 + 1
n = 6
1번 for문: 1 to 4 -> 4번
2번 for문
2 to 5 -> 4번
3 to 5 -> 3번
4 to 5 -> 2번
5 to 5 -> 1번
3번 for문
4 + 3 + 2 + 1번
3 + 2 + 1번
2 + 1번
1번
수행 횟수 20 = 10 + 6 + 3 + 1
n = 5
1번 for문: 1 to 3 -> 3번
2번 for문
2 to 4 -> 3번
3 to 4 -> 2번
4 to 4 -> 1번
3번 for문
3 + 2 + 1번
2 + 1번
1번
수행 횟수 10 = 6 + 3 + 1
5에 10 // 6에 20 // 7에 35
그리고 이 수가 나오는 규칙은 (n - 2)(n - 1)n / 6
'백준 알고리즘 문제 기록 > 시간 복잡도' 카테고리의 다른 글
| 백준 Swift [24313] 알고리즘 수업 - 점근적 표기 1 (0) | 2023.07.03 |
|---|---|
| 백준 Swift [24266] 알고리즘 수업 - 알고리즘의 수행 시간 5 (0) | 2023.07.03 |
| 백준 Swift [24265] 알고리즘 수업 - 알고리즘의 수행 시간 4 (0) | 2023.07.03 |
| 백준 Swift [24264] 알고리즘 수업 - 알고리즘의 수행 시간 3 (0) | 2023.07.03 |
| 백준 Swift [24263] 알고리즘 수업 - 알고리즘의 수행 시간 2 (0) | 2023.07.03 |
