알고리즘/전처리

알고리즘 테크닉 - 런타임 전의 전처리 기법

1. 런타임 전의 전처리(preprocessing)

 

실제 문제를 해결하는 프로그램을 작성하기 전에, 해당 프로그램의 핵심을 얻기 위한 다른 프로그램을 미리 작성하여 원하는 값을 구해놓고, 문제를 해결하는 프로그램을 작성하는 기법

 

프로그램 안에 원하는 값을 계산하는 코드를 작성하지 않고, 미리 필요한 값을 계산해놓은 다음에 실제 프로그램에서 시간복잡도를 줄이는 기법이다.

 

이런 기법은 사실 알게모르게 많이 써왔다..

 

최근에 이것이 핵심인?문제를 풀어서 복기해본다

 

(태그는 이분탐색이었지만)

 

2. 문제

 

4030번: 포켓볼 (acmicpc.net)

 

4030번: 포켓볼

선영이는 당구대를 상근이에게 빌렸다. 상근이는 선영이에게 공 16개가 들어갈 수 있는 4×4 크기의 트레이도 같이 주었다. 이 트레이는 그림 (a)와 같이 생겼다. 흰색 공은 큐 볼이고, 나머지 15개

www.acmicpc.net

 

요약하자면, a와 b 사이에서 x+1이 제곱수이면서, x는 1부터 특정한 수 n까지의 합인 경우인 x+1의 개수를 구하는 문제이다.

 

"1부터 특정한 수 n까지의 합"인 경우는 무엇일까

 

1, 1+2, 1+2+3, 1+2+3+4, ...

 

1,3,6,10,....

 

결국 이는 1부터 n까지의 배열에서 누적합 배열을 만들면, 그것이 x로서 가능한 후보가 들어간 배열이 된다.

 

x의 가능한 범위는 어디까지일까

 

a,b가 1부터 10의 9제곱까지이므로, x도 당연히 10의 9제곱까지이다.

 

누적합이 들어간 배열의 원소가 10의 9제곱까지 될려면... 1부터 45000정도까지 더해주면 되더라고...

 

정확히는 44721까지인가? 근데 제출할 프로그램이 아니라 대충 45000까지 해도 상관은 없지

 

arr = list(range(1,44722))

power = []

for i in range(44720):
    
    arr[i+1] += arr[i]

print(arr[-1])
1000006281

 

그러면 arr에는 x로서 가능한 원소들이 들어있다.

 

그러면 이제 x+1이 제곱수인지 판단하고, 제곱수라면 x+1을 어떤 배열 power안에 넣어둔다면...

 

그것이 문제에서 요구하 우리가 찾고자하는 후보값들이 된다

 

arr = list(range(1,44722))

power = []

for i in range(44720):
    
    arr[i+1] += arr[i]

    x = arr[i+1]

    z = int((x+1)**(1/2))

    if z**2 == x+1:
        
        power.append(x+1)

print(power)
[4, 16, 121, 529, 4096, 17956, 139129, 609961, 4726276, 20720704, 160554241, 703893961]

 

놀랍게도 10의 9제곱 이내에서 문제의 조건을 만족하는 x+1은.. 12개밖에 없다!!!

 

실제 문제를 해결하는 프로그램을 제출할때는...  미리 구해놓은

 

[4, 16, 121, 529, 4096, 17956, 139129, 609961, 4726276, 20720704, 160554241, 703893961]을 쓰면 그만이다.

 

그러니까 a,b를 받고 위 배열을 순회해서 a,b사이에 들어가면 count에 1을 더해주면 끝이지

 

from sys import stdin

power = [4, 16, 121, 529, 4096, 17956, 139129, 609961, 4726276, 20720704, 160554241, 703893961]

n = 1

while 1:
    
    a,b = map(int,stdin.readline().split())

    if a == 0 and b == 0:
        
        break

    count = 0

    for p in power:
        
        if p > a and p < b:
            
            count += 1
    
    print(f"Case {n}: {count}")

    n += 1

 

 

 

TAGS.

Comments