본문 바로가기

카테고리 없음

[백준 15824번] 너 봄에는 캡사이신이 맛있단다 (Python3)

재미있는 문제였다.

이 문제는 특이하게도 N의 범위에 따라서 점수를 따로 측정하였다. easy 버전과 hard 버전이 있는 문제들이 많은데 그걸 한 문제로 합쳐놓은 것 같은 문제였다.

 

처음에 내가 제출한 코드는 이러했다. 

import sys
input = sys.stdin.readline
mod = 1000000007

N = int(input())
food = [*map(int,input().split())]
food.sort()

cal = {i:1 for i in range(N-1)}
for i in range(1,N-1):
  cal[i] = cal[i-1]*2%mod

result = 0
for i in range(N):
  for j in range(i+1,N):
    result += (food[j]-food[i])%mod*cal[j-i-1]
    result %= mod

print(result)

시간복잡도가 O(N^2)인 코드로, 그냥 단순하게 이중 for문을 돌리는 코드이다.

그랬더니 small 버전만 통과가 되어 50점을 받았다. 

 

그렇게 공책에 끄적끄적 해보다가 중요한 사실을 발견했는데 식을 두 요소의 차이를 가지고 하는게 아니라 한 요소의 값에 대해서 쓸 수 있다는 것을 알게되었다.

이를 반영한 코드는 다음과 같다.

 

import sys
input = sys.stdin.readline
mod = 1000000007

N = int(input())
food = [*map(int,input().split())]
food.sort()

cal = {i:1 for i in range(N)}
for i in range(1,N):
  cal[i] = cal[i-1]*2%mod

result = 0
for i in range(N):
  result -= food[i]%mod * cal[N-1-i]
  result += food[i]%mod * cal[i]
  result %= mod

print(result)

 

한 요소가 모든 조합에 미치는 영향은 (2^i)-(2^(N-1-i)) 이라는 사실을 조합을 생각하면 쉽게 구할 수 있는데 이를 이용한 코드이다.

결과값을 내는 과정은 시간복잡도 O(N)으로 구현 가능했고, sort하는 과정이 있으니 전체 시간복잡도는 O(NlogN)일 것이다. 이 코드로 제출하자 250점을 받을 수 있었다.

 

 

오늘의 교훈) 시간복잡도를 최대한 줄일 수 있는 방법을 생각하자.