[python] 가게 입점 시키기

문제

실행시간 제한 : 30sec

 

요약하자면, start와 end를 입력받고 두 수에 존재하는 a=b+c인 경우의 수를 모두 찾아 개수를 구하는 문제이다.

 

입력의 크기를 시간 복잡도에 대입해서 얻은 반복문 수행 횟수에 대해, 1초 당 반복문 수행 횟수가 1억(10^8)을 넘어가면 시간 제한을 초과할 가능성이 있다.

 

 

시간제한이 1초인 문제를 만났을 때, 일반적인 기준은 다음과 같습니다.

입력이 10,000,000 개의 경우: O(N) 알고리즘

입력이 50,000 개인 경우: O(N * log N) 알고리즘

입력이 10,000 개인 경우: O(N * N) 알고리즘

입력이 400개: O(N * N * N) 알고리즘

 

입력의 최댓값이 1,000,000 이기 때문에, O(n) 알고리즘의 경우 0.1 초가 걸릴것이고

300 * O(n) = 30초 , 따라서 최소 300 * O(n) 안의 시간에 수행을 완료해야 한다.

 

가장 기본적인 풀이로는 삼중 for문으로 ㄴstart부터 end 까지 반복 후,  a=b+c인 값을 찾으면 되겠지만.

for a in range(start, end + 1):
    for b in range(start, end + 1):
        for c in range(start, end + 1):
            if b + c == a:
            	cnt+=1
print(cnt)

이 경우 최대 1,000,000^3 = 10^18에 해당하는 연산을 수행해야 하며, 이는 10^11 초 가량 소요되는 끔찍한 코드일 것이다.

 

 

여러 시도를 해보았지만, 30초 안에 수행해내는 코드를 작성하기가 힘들었다..

#실패코드 1
start = int(input(""))
end = int(input(""))
cnt = 0

for i in range(start, end + 1):
    for j in range(start, i):
        k = i - j
        if start <= k <= end:
            cnt += 1

print(cnt)

# 실패코드 2
import numpy as np

start = int(input(""))
end = int(input(""))

cnt = 0
values = np.arange(start, end + 1)

for i in values:
    j_values = values[values < i]
    k_values = i - j_values
    cnt += np.sum(np.logical_and(k_values >= start, k_values <= end))

print(cnt)

 

두 코드 모두 어림도 없이 타임아웃이 나왔고, 당연히 타임아웃 나올걸 알았지만 괜히 기대하게되는 말도안되는 희망을 품는 나의 멍청함에 다시금 감탄했다!

 

이후 규칙을 찾아 접근해야 할 문제 같아서,  시도해 보았다.

우선 start를 고정시키고 end에 대한 규칙을 살표보았다.

start	end	result
1	10	45
1	100	4950
1	1000	499500

 

아주 익숙한 패턴이 보인다. 1~end까지의 합에서 end값을 뺀 값이라는 걸 알 수 있다.

즉. end*(end+1)/2-end 라는 식으로 간단히 정리가 가능하다.(가우스 등차수열 합)

 

그렇다면, 이제 start의 규칙을 찾아보겠다.

start	end	result	change
1	10	45
2	10	28	17
3	10	15	13
4	10	6	9

언뜻 보면 규칙이 없어 보일 수 있지만 그렇지 않다. 

start 값이 증가합에 따라 17, 13, 9 씩 result가 변화하였고 이는 공차가 -4인 공차수열의 형태를 띄고있는 것을 알 수 있다.

an = 17 -4*(n-1),  여기서 n = start-1

 

위와 같이 start, end에 따른 result의 변화를 알았으니 정리하자면,

(1,end) 에 대한 result를 구하고 그 값에서,

start가 2,3,4,,,,, start 값이 될때까지 change값의 총 합을 구한 후, result 값에서 빼주면 답이 될 것이다.

 

코드는 아래와 같다.

 

start = int(input(""))
end = int(input(""))
cnt=0
result = end*(end+1)/2-end
for i in range(1,start):
    result -= 2*end -4*(start-cnt)+5
    cnt+=1
    
print(int(result))

 

 

 

코딩테스트 준비를 시작하기에 앞서, 갑자기 눈에 들어와서 시도를 해 본 문제인데

이것이 어떤 유형의 문제인지도 모를 만큼 무지한 상태이다...

따라서, 이론 공부를 마친 뒤 다시 와서 정석적인 방법으로 시도해 보도록 하자..!

 

 

이 문제에 대한 다른 풀이나 아이디어가 있으신 분, 어떤 유형의 문제인지 아시는 분은 댓글로 남겨 공유 부탁드립니다!!!