[백준알고리즘] 2632번: 피자판매 -Python

[백준알고리즘] 2632번: 피자판매 -Python

https://www.acmicpc.net/problem/2632

2632번: 피자판매

두 가지 방법으로 문제를 풀었다.

 

첫 번째 방법은 기존에 이런 유형의 문제를 풀기 위해서 많이 사용했던 방법이다.

A피자에서 가능한 연속합, B피자에서 가능한 연속합을 모두 구한 뒤 양쪽에서 하나씩 연속합을 선택하는 것이다.

이 방법으로는 PyPy까지만 통과가 가능했고, Python에서는 시간 초과가 발생했다.

두 번째 방법은 다 풀고 다른 분들의 코드는 훨씬 짧은 시간 내에 통과했길래 보고 참조한 코드이다. 특히 cubelover님의 코드가 가장 간단하면서 짧은 시간 안에도 통과해서 참조했다.

다른 분들은 첫번째 풀었던 방법과 사용한 개념은 같았지만 투 포인터를 이용해 검색한 것이 아닌 딕셔너리를 통해 동일한 연속 합의 개수를 카운트했다. (cubelover님은 리스트를 통해 사용하셨다.)

 

 

첫 번째 방법

각각 양쪽 피자판에서 연속합으로 구할 수 있는 크기를 모두 구했다.

피자판은 둥글기 때문에 시작점이 i에 위치해있다고 하더라도 한 바퀴 돌아서 연속합을 만들 수 있다. 즉, i-1번째 조각만 제외한 연속합을 만들 수 있다. 따라서 이 부분에서도 O(N^2)의 시간이 지나게 된다.

 

이렇게 각각 구한 연속합을 크기순으로 정렬하고 투 포인터 알고리즘을 이용했다. 하나의 피자판에서는 작은 연속합부터, 반대쪽 피자판에서는 큰 연속 합부터 인덱싱 해나 가면서 요구하는 크기와 일치하는 두 연속 합의 합의 개수를 구했다.

포인터를 이용해주었기 때문에 현재의 값과 일치하는 값의 개수 또한 반복문을 통해서 카운트해주었다.

 

이 코드는 Python에서는 통과하지 못했고, PyPy에서만 통과했다. 그것도, 목표양보다 많은 양일 경우 continue를 해주는 코드를 삽입해서 필요 없는 부분을 더 제외시켜줌으로써 겨우 통과했다. continue를 추가하기 전에는 PyPy도 시간 초과가 발생했다.

import sys

target = int(sys.stdin.readline().rstrip())
m, n = map(int, sys.stdin.readline().split())
left = [int(sys.stdin.readline().rstrip()) for _ in range(m)]
right = [int(sys.stdin.readline().rstrip()) for _ in range(n)]

lsum, rsum = [0, sum(left)], [0, sum(right)]
for i in range(m):
    for j in range(m):
        if i == j:
            continue
        elif i < j <= m:
            tmp = sum(left[i:j])
            if tmp > target:
                continue
            lsum.append(tmp)
        else: # j < i
            tmp = sum(left[i:] + left[:j])
            if tmp > target:
                continue
            lsum.append(tmp)
for i in range(n):
    for j in range(n):
        if i == j:
            continue
        elif i < j <= n:
            tmp = sum(right[i:j])
            if tmp > target:
                continue
            rsum.append(tmp)
        else: # j < i
            tmp = sum(right[i:] + right[:j])
            if tmp > target:
                continue
            rsum.append(tmp)
lsum.sort()
rsum.sort()

ans = 0
lleft, lright = len(lsum), len(rsum)
lp, rp = 0, lright-1
while lp < lleft and rp >= 0:
    tmp = lsum[lp] + rsum[rp]

    if tmp == target:
        lcnt, rcnt = 0, 0
        origin = lsum[lp]
        while lp < lleft and origin == lsum[lp]:
            lcnt += 1
            lp += 1
        origin = rsum[rp]
        while rp >= 0 and origin == rsum[rp]:
            rcnt += 1
            rp -= 1

        ans += (lcnt * rcnt)

    elif tmp < target:
        lp += 1
    else: #tmp > target
        rp -= 1

print(ans)

 

두 번째 방법

cubelover님의 코드를 보고 나서 코드를 짜다 보니 거의 같게 작성된 것 같다. 아이디어가 같으면 달라질 코드 부분도 없긴 하지만..

 

어차피 목표 양이 2,000,000 이하로 주어지기 때문에 각각의 연속합을 체크해줄 배열의 크기도 2,000,001로 잡아주었다. 또한 목표 양보다 많아지는 경우는 바로바로 스킵해주었다.

 

그렇게 양쪽에서 가능한 연속합을 체크해주었다. 같은 연속합이 여러 가지 존재할 경우에는 증가시켜줌으로써 그 개수를 유지해주었다.

import sys

target = int(sys.stdin.readline().rstrip())
m, n = map(int, sys.stdin.readline().split())
left = [int(sys.stdin.readline().rstrip()) for _ in range(m)]
right = [int(sys.stdin.readline().rstrip()) for _ in range(n)]

lsum, rsum = [0]*2000001, [0]*2000001
lsum[0] = rsum[0] = 1
llen, rlen = len(left), len(right)
for i in range(llen):
    s = 0
    for j in range(llen):
        s += left[(i+j)%m]
        if s > target:
            break
        else:
            lsum[s] += 1
for i in range(rlen):
    s = 0
    for j in range(rlen):
        s += right[(i+j)%n]
        if s > target:
            break
        else:
            rsum[s] += 1
lsum[sum(left)] = rsum[sum(right)] = 1

ans = 0
for i in range(target+1):
    ans += (lsum[i] * rsum[target-i])
print(ans)

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다