내 코드
n = int(input())
print((n-1) * n // 2)
print(2)
이 문제 풀면서 정말 어려웠다... 처음에는 문제가 이해가 되지 않아서 여러번 읽어봤고, 그래도 어떻게 해야할지 몰랐는데 시간복잡도를 찾아보면서 이해할 수 있었다.
문제에서 요구하는 것은 코드 1의 수행 횟수, 즉 이중 for 문 내부의 sum이 몇번이나 실행되는지를 말하는 것이다.
그렇다면 바깥쪽 for문의 반복 횟수 X 안쪽 for문의 반복 횟수를 해주면 답이 나온다.
바깥쪽 for 문의 i는 1부터 n - 1까지 반복된다. 그리고 안쪽 for 문의 j는 i + 1부터 n까지 반복된다. 예제처럼 n이 7이라고 할 경우, 반복되는 내용을 정리해보면 이렇다.
- i가 1일때 - j는 2 ~ 7까지 반복 (6회)
- i가 2일때 - j는 3 ~ 7까지 반복 (5회)
- i가 3일때 - j는 4 ~ 7까지 반복 (4회)
- i가 4일때 - j는 5 ~ 7까지 반복 (3회)
- i가 5일때 - j는 6 ~ 7까지 반복 (2회)
- i가 6일때 - j는 7만 수행 (1회)
즉 j가 반복되는 횟수는 (n-1), (n-2)... 1이 된다. 이 횟수의 합을 구하기 위해서는 등차 수열의 합 공식을 사용할 수 있다. 그래서 첫 줄에 출력되는 내용은 (n-1) * n // 2가 되는 것이다.
그럼 두번째 줄은 무슨 뜻일까? 많은 블로그들을 찾아봤지만 곧바로 이해하기는 쉽지 않았다😢
검색해본 결과 시간 복잡도를 묻는 내용이었고, 빅오 표기법으로 표기해보자면 이 알고리즘은 O(n^2)의 복잡도를 가진다. 그래서 둘째줄에는 2가 출력된다.
시간 복잡도를 이해해야하고 등차수열의 합을 알아야해서 푸는데 시간이 걸린 문제였다.
https://www.acmicpc.net/problem/24265
'study > Algorithm' 카테고리의 다른 글
[백준] 파이썬 10816 : 숫자 카드 2 (0) | 2024.03.30 |
---|---|
[백준] 파이썬 24267 : 알고리즘의 수행시간 6 (0) | 2024.03.30 |
[백준] 파이썬 11478번 : 서로 다른 부분 문자열의 개수 (0) | 2024.03.28 |
[백준] 파이썬 20291번 : 파일 정리 (0) | 2024.03.28 |
[백준] 파이썬 7785번 : 회사에 있는 사람 (0) | 2024.03.28 |