백준 15824 - 너 봄에는 캡사이신이 맛있단다 (Python)

https://acmicpc.net/problem/15824 

15824번: 너 봄에는 캡사이신이 맛있단다

이번 주동안 생각해보면서 여러모로 많이 틀리고 많이 배웠던 문제. 이항계수의 합을 공부하면서 쉽게 풀 수 있다는 생각을 했지만 아니었다. 이항계수의 합은 2**n이다. 기억하자.

오답 풀이 1.

import sys
from itertools import combinations
input=sys.stdin.readline

def mul(i):
    if i==0:
        return 1
    if i%2==0:
        return (mul(i//2)**2)%mod
    else:
        return (2*mul((i-1)//2)**2)%mod

mod=1000000007
answer=0

N=int(input())
l=list(map(int,input().split()))

combs=combinations([i for i in range(N)],2)
for a,b in combs:
    if a>b:
        a,b=b,a
    elif l[a]==l[b]:
        continue
    answer+=(l[b]-l[a])*mul(b-a-1)
    answer%=mod

print(answer)

이렇게 풀면 안 되는 이유가 여러 가지 있지만, 여기서 알게 된 점은 굳이 combination을 쓸 필요가 없단 점.

오답 풀이 2. pow가 있다는 사실을 알게 되어 이용하여 써 보았다. 다만 이 pow는 거듭제곱을 이용한 방식이 아니다. 내장 pow는 그렇게 구현되어 있지 않으니 내가 임의로 구현해야 한다는 사실을 알게 되었다. 나머지가 세 번째 argument에 들어가서 나머지 연산이 바로 된다는 것이 좋은 점이었다.

import sys
input=sys.stdin.readline

mod=1000000007
answer=0

N=int(input())
l=list(map(int,input().split()))
l.sort()

for a in range(N-1):
    for b in range(a+1,N):
        if l[a]==l[b]:
            continue
        answer+=((l[b]-l[a])*pow(2,b-a-1,mod))%mod

print(answer%mod)

마찬가지로 여러 틀린 점이 있었지만, 여기서 pow의 구현 외에도 틀린 점은 저렇게 포인터를 두 개 두면 시간 초과로 풀 수 없다는 점. 당연히 생각은 하고 있었지만 마땅한 방법이 생각이 안 났다….

정해.

import sys
input=sys.stdin.readline

def pow(a,b,c):
    if b==0:
        return 1
    if b==1 :
        return a%c
    if b%2==0:
        return pow(a**2%c,b//2,c)
    else:
        return a*pow(a**2%c,b//2,c)%c

mod=1000000007
p,m=0,0

N=int(input())
l=list(map(int,input().split()))
l.sort()

for i in range(N):
    p+=l[i]*pow(2,i,mod)
    m+=l[i]*pow(2,N-i-1,mod)
    p%=mod

print((p-m)%mod)

결국 문제를 푸는 방법은, 조합론에 대한 생각에서 왔다. 내가 i번째 숫자를 볼 때 i가 최댓값인 조합은 i 이전 번째 모든 숫자다. 마찬가지 원리로 i가 최솟값인 조합은 i 이후 모든 숫자다. 하나하나 같이 따지느니, 숫자 하나를 볼 때 -들과 +들을 따로따로 더해주면, O(n)에 모든 숫자를 볼 수 있다.

여기서 또 꽤나 중요한 깨달음을 얻었는데, 나머지 연산을 하기에는 상향식으로 2부터 곱연산을 하는 것이 편하다는 사실이었다. 왜냐하면 나머지 연산을 언제 해 줄지가 헷갈리기도 하고, 곱연산이 무조건 더 빠르니까.

번외: 이런 문제가 나올 때, 300000까지 그냥 제곱 값을 미리 리스트에 넣어 놓으면 매번 연산할 필요도 없다.