귀찮음
| ps | |
|---|---|
| 링크 | acmicpc.net/… |
| 출처 | BOJ |
| 문제 번호 | 16208 |
| 문제명 | 귀찮음 |
| 레벨 | 실버 5 |
| 분류 |
애드혹 |
| 시간복잡도 | O(n) |
| 인풋사이즈 | n<=500,000 |
| 사용한 언어 | Python 3.13 |
| 제출기록 | 63380KB / 152ms |
| 최고기록 | 136ms |
| 해결날짜 | 2026/03/04 |
풀이
- 1개에서 시작해서 n개로 자르는 문제이지만, n개에서 시작해서 1개로 합치는 문제로 바꿔도 달라지는 것은 없다.
- 이렇게 바꾸고 나면
슬라임 합치기과 동일한 문제가 된다. 어떤 순서로 합치든 총 비용은 동일하다. - 그러므로 그냥 순서대로 합쳐보고 얻은 비용을 그대로 출력하면 끝. 시간복잡도는 O(n)
코드
"""Solution code for "BOJ 16208. 귀찮음".
- Problem link: https://www.acmicpc.net/problem/16208
- Solution link: http://www.teferi.net/ps/problems/boj/16208
Tags: [ad hoc]
"""
def main():
_n = int(input())
a = [int(x) for x in input().split()]
answer = 0
l = 0
for a_i in a:
answer += l * a_i
l += a_i
print(answer)
if __name__ == '__main__':
main()