[백준/25553] 단짠단짠 피자 (Python)

Problem : https://www.acmicpc.net/problem/25553

25553번: 단짠단짠 피자

 

Difficulty : Gold 1

 

Status : Solved

 

Time : 00:09:28

 

---

 

문제 설명

 

 

N개의 조각으로 이루어진 원형의 피자가 있다. 각 조각은 시계방향으로 1번부터 N번까지의 번호를 가지고 있으며, 피자가 원형이기 때문에 N번 조각 다음에는 1번 조각이 있다. 각 조각은 번호별로 종류가 다른데, 홀수 번호에 해당하는 조각은 파인애플 피자, 짝수 번호에 해당하는 조각은 페퍼로니 피자이다. 초기에 i번째 조각은 A_i만큼의 맛 수치를 가지고 있다. 포닉스는 지금 배가 매우 고프기 때문에 연속된 K개의 조각을 집어 한번에 먹으려 한다. 특정 조각에서 시작해 시계방향으로 연속된 K개의 조각을 먹었을 때 속한 조각의 맛의 합을 만족도라 하자. 포닉스는 만족도가 최대가 되게 하는 시작 조각을 선택하며, 만약 이러한 조각이 여럿일 경우 번호가 가장 작은 조각을 시작 조각으로 선택한다. 이때, Q개의 작업이 주어진다. 각 작업은 다음 세 가지 중 하나이다.

 

1 x : 모든 파인애플 피자 조각 (홀수 번째 조각)의 맛 수치를 x만큼 증가시킨다.
2 x : 모든 페퍼로니 피자 조각 (짝수 번째 조각)의 맛 수치를 x만큼 증가시킨다.
3 : 현재의 피자 상태에서 포닉스가 선택할 시작 조각의 번호와 해당 조각을 시작 조각으로 했을 때의 만족도를 공백으로 구분해 출력한다. 3번 작업으로 인해 피자의 상태가 변화하지는 않는다.

 

배가 고픈 포닉스를 위해 주어지는 작업을 올바르게 처리하는 프로그램을 작성하여라.

 

 

입력 및 출력

 

입력

 

첫째 줄에 피자 조각의 수 N, 작업의 수 Q, 한번에 먹을 조각의 수 K가 주어진다. 
(1 <= K <= N <= 200,000, 1 <= Q <= 200,000)
둘째 줄에는 각 조각의 초기 맛 A_i가 공백으로 구분되어 주어진다. 
(-100,000 <= A_i <= 100,000) 
셋째 줄부터 Q줄에 걸쳐 처리해야 할 작업이 t x 또는 t 형식으로 주어진다. 3번 작업이 최소 한 번 주어짐이 보장된다. 
(t in {1, 2, 3}, -100,000 <= x <= 100,000)
주어지는 수는 모두 정수이다.

 

출력

 

각 3번 작업에 대한 답을 입력된 순서대로 한 줄에 하나씩 출력한다.

 

입력 예시

 

4 3 3
2 -5 3 -4
3
2 10
3

 

출력 예시

 

3 1
2 14

 

 

---

 

풀이

 

쿼리에 따라 일일히 모든 홀수 및 짝수를 조작하고, 모든 만족도를 구할 필요는 없다. 원본 값은 변하지 않고, 그 i번째 조각에 포함된 홀수와 짝수의 개수는 모두 같으므로 (홀수의 개수*증가한 홀수 맛수치 + 짝수의 개수*증가한 짝수 맛수치)를 나중에 더해주기만 하면 된다.

 

즉 3번 쿼리의 만족도를 구할 때마다 같은 홀수 및 짝수 개수를 가진 타입들은 동일한 순서를 지닌다. 홀수, 짝수의 개수가 같으므로 항상 같은 값이 업데이트되기 때문이다. 즉 같은 (홀수, 짝수) 타입마다 원본 값의 최대치와 이에 해당하는 인덱스를 저장한다면 빠르게 쿼리를 처리할 수 있다.

 

또한, 이 (홀수, 짝수) 패턴은 기껏해야 최대 3개이다. i번째 윈도우부터 K 크기의 슬라이딩 윈도우로 탐색한다고 가정하자.

• 슬라이딩 윈도우가 리스트 내에 있을 경우
  • 시작점 < 끝점을 만족한다.
  • 이 경우는 (K//2 + K%2, K//2) 혹은 (K//2, K//2 + K%2)개의 홀수, 짝수가 유지된다. 슬라이딩 윈도우를 한 칸 오른쪽으로 옮기고, 이 슬라이딩 윈도우 역시 리스트 내에 있을 경우 (-K%2, +K%2) 혹은 (+K%2, -K%2)으로 업데이트된다. 최대 2가지 경우의 수를 가진다.
• 슬라이딩 윈도우가 리스트 외부에 있을 경우
  • 시작점 > 끝점을 만족한다.
  • N이 짝수라면 리스트 내에 있을 때와 동일하다. [1, 0, 1, 0, ..., 1, 0] [1, 0, 1, 0, ] 순으로 홀수-짝수 등장의 연속성이 지켜진다.
  • N이 홀수라면, (K//2 + K%2 + 1, K//2  - 1) 혹은 (K//2 + K%2, K//2 )의 경우의 수를 가진다.
    • N이 홀수이므로 리스트 내의 마지막 슬라이딩 윈도우는 (K//2 + K%2, K//2)꼴이 된다.
    • 이후, 연속성이 깨지는 상황이 발생한다 (리스트 내 마지막 원소는 홀수번째이고, 다음 원소가 홀수번째임)
    • 즉 기존 패턴을 고정한 채 새로운 연속성 규칙에 따라 (+1, -1) 혹은 (-1, +1)로 업데이트된다.

 

즉 초기화에 O(N), 그리고 쿼리 하나 처리에 O(1)이 소요되므로 총 시간복잡도는 O(N + Q)가 된다.

 

 

풀이 코드

import sys
input = sys.stdin.readline

ans = -1
N, M = map(int, input().split())
maps = [input().strip() for _ in range(N)]

for i in range(N) :
  for j in range(M) :
    for k in range(-N, N) :
      for l in range(-M, M) :
        if not k and not l :
          continue
        _i, _j, tmp = i, j, ''
        while -1 < _i < N and -1 < _j < M :
          tmp += maps[_i][_j]
          if int(int(tmp) ** 0.5) ** 2 == int(tmp) :
            ans = max(ans, int(tmp))
          _i += k
          _j += l
print(ans)

풀이 완료!