[ BOJ ] 10836 : 여왕벌 ( GOLD 4 ) / Python

>> 문제 바로가기 (https://www.acmicpc.net/problem/10836)

문제

크기가 M×M인 격자 형태의 벌집이 있다. 이 벌집의 각 칸에는 여왕벌이 될 애벌레들이 한 마리씩 자라고 있다. 

격자칸의 좌표계를 다음과 같이 설정한다. 제일 왼쪽 위 칸의 좌표는 (0,0)이다. 그 아래쪽 칸들의 좌표는 순서대로 (1,0), (2,0), ...등이다. 좌표가 (i,0)인 칸의 오른쪽 칸들의 좌표는 순서대로 (i, 1), (i,2), ... 등이다. 

애벌레들은 매일 에너지를 모아서 정오(낮 12시) 에 한번 자라는데, 여기에 걸리는 시간은 매우 짧아서 무시할 수 있다. 첫날 아침 모든 애벌레들의 크기는 1이고, 이러한 과정을 N일 동안 반복한다. 

각 애벌레가 자라서 크기가 커지는 정도는 하루에 +0, +1, +2의 세 가지 중 하나이다. 더하기(+) 기호는 앞으로 생략한다. 구체적으로 각 애벌레가 자라는 정도를 결정하는 규칙은 다음과 같다.

1. 제일 왼쪽 열과, 제일 위쪽 행의 애벌레들은 자신이 자라는 정도를 스스로 결정한다. 이들은 입력으로 주어질 것이다. 애벌레들이 자라는 정도를 왼쪽 제일 아래 칸에서 시작하여 위쪽으로 가면서 읽고, 제일 위쪽 칸에 도착하면 오른쪽으로 가면서 행의 끝까지 읽었다고 하자. 모든 입력에서 이렇게 읽은 값들은 감소하지 않는 형태이다.
2. 나머지 애벌레들은 자신의 왼쪽(L), 왼쪽 위(D), 위쪽(U)의 애벌레들이 다 자란 다음, 그 날 가장 많이 자란 애벌레가 자란 만큼 자신도 자란다. 

M = 4, N = 2인 예를 하나 들어보자. 다음은 각 격자에 있는 애벌레의 첫날 아침의 크기이다.

1	1	1	1
1	1	1	1
1	1	1	1
1	1	1	1

2일 동안 제일 왼쪽 열과 제일 위쪽 행에 있는 7마리의 애벌레들이 자라는 정도를 왼쪽 제일 아래칸에서 시작하여 위쪽으로 가면서 읽고, 제일 위쪽 칸에 도착하면 오른쪽으로 가면서 행의 끝까지 읽었을 때, 다음과 같다고 하자. 

• 1일: 0, 0, 1, 1, 1, 2, 2
• 2일: 1, 1, 1, 1, 1, 1, 2

첫날 저녁에 애벌레들은 아래와 같은 크기를 가진다. 예를 들어, 좌표 (1,1)의 애벌레는 왼쪽 애벌레의 크기가 1만큼 자랐고, 왼쪽 위의 애벌레가 1만큼 자랐고, 위쪽 애벌레도 1만큼 자랐으므로, 자신도 1만큼을 자란다. 또, 좌표 (3,3)의 애벌레는 규칙을 따르면 2만큼 자람을 알 수 있다.

2	2	3	3
2	2	3	3
1	2	3	3
1	2	3	3

둘째 날이 지났을 때는 동일한 과정에 따라 다음과 같이 됨을 확인할 수 있다.

3	3	4	5
3	3	4	5
2	3	4	5
2	3	4	5

격자칸의 크기, 날자 수, 날자별 제일 왼쪽 열과 제일 위쪽 행의 애벌레들이 자라는 정도를 입력으로 받아 마지막 날 저녁의 애벌레들의 크기를 출력하는 프로그램을 작성하라

입력

입력의 첫 줄에는 격자칸의 가로와 세로 크기 M(2 ≤ M ≤ 700)과 날짜 수 N(1 ≤ N ≤ 1,000,000)이 자연수로 주어진다. 첫날 아침의 애벌레 크기는 모두 1이므로 입력에 주어지지 않는다. 다음 N개의 줄에는 첫날부터 순서대로 제일 왼쪽 열과 제일 위쪽 행의 애벌레들이 자라는 정도가 다음의 형식으로 주어진다. 본문에서 보인 것과 같이, 자라는 크기를 제일 왼쪽 아래 칸에서 시작해서 위쪽으로 올라가서 제일 위쪽에 도착하면 오른쪽으로 이동하며 읽었다고 하자. 이 값들은 감소하지 않는다. 따라서, 이 수열을 처음부터 읽었을 때 0의 개수, 1의 개수, 2의 개수를 순서대로 입력에 준다. 하루에 대해서 이 세 개수들의 합은 2M-1임이 자명하다. 세 값들 중에 0이 있을 수 있다

출력

M개의 줄에 각각 M개의 자연수를 출력한다. 이는 각 애벌레의 마지막 날 저녁의 크기를 첫 행부터, 각 행에서는 왼쪽부터 제시한 것이다. (본문의 예와 동일한 형태이다.) 

풀이 과정

날짜 수 제한이 1,000,000 까지이다... 단순 시뮬레이션으로 격자칸 700 x 700 을 날짜마다 순회하면 시간 제한이 걸리므로 O(N) 안에 해결할 수 있는 방법을 생각해 내야 한다.

 

1. 가장자리 처리

 

먼저, 제일 왼쪽 열과 제일 위쪽 행의 애벌레 들을 가장자리라고 칭한다.

 

입력으로 들어오는 애벌레 +0 증가, +1 증가, +2 증가는 개수로 들어오므로, 가장자리마다 하나하나씩 증가하면 되겠지 싶어도, 최대 가장자리의 길이는 2M - 1 이기 때문에 하나하나씩 추가하는 방법은 시간 초과가 발생한다.

 

그렇기에, 날마다 증가하는 증가 개수 배열을 0 증가가 끝나는 위치, 1 증가가 끝나는 위치, 2 증가가 끝나는 위치로써 누적합으로 바꿔 저장한 다음, 1 증가가 시작되는 위치부터 1을 증가시키고, 2 증가가 시작되는 위치부터 2를 증가시켜 이후에 차례대로 누적하는 방식을 통해 가장자리를 한 번에 만드는 방법을 사용했다.

 

0

0

0

0

0

0

0

다음 표가 가장자리 왼쪽 아래 부터 오른쪽 위까지의 증가량이라고 할 때, 증가 개수가 2 3 2 로 들어온다면,

 

0

0

1

1

1

2

2

가 증가되어야 한다.

 

이때, 하나하나씩 증가시키는 것이 아니라 시작 위치에만 증가시키고 나중에만 누적시킨다면?

2 3 2 배열을 -> 2 5 7 배열로 만든 뒤, 

0 증가가 끝나는 위치, 1 증가가 끝나는 위치 는 각각 1 증가가 시작되는 위치, 2 증가가 시작되는 위치와 같으므로

 

0

0

1 (1 시작 위치)

0

0

1 (2 시작 위치)

0

이렇게 1 씩만 증가시켜준 이후 가장자리 배열을 탐색하여 누적합 배열로 만들면

0

0

1

1

1

2

2

하나하나씩 증가시키는 방식과 결과가 동일해진다.

 

여기서 추가로 생각해야 하는 부분은 바로 특정 증가 개수가 0인 경우이다.

이는 다양한 경우가 있으므로, 케이스를 하나씩 살펴보자.

 

1. 0이 0개일때 : 0이 0개일 때의 입력은 다음과 같이 들어온다. [ 0 2 3 ], [ 0 1 2 ]
   하지만 누적합으로 만들어도 1이 시작되는 위치는 결국 0이므로 상관없다.
   
   
2. 1이 0개일때 : 1이 0개일 때의 입력은 다음과 같이 들어온다. [ 1 0 3 ], [ 2 0 6 ]
   이런 배열이 입력으로 들어올 때 누적합을 만들면 [ 1 1 4 ], [ 2 2 8 ] 이 된다.
   0 증가가 끝나는 위치와 1 증가가 끝나는 위치가 같다면 1을 증가시키지 않는다.
   
   
3. 2가 0개일때 : 2가 0개일 때의 입력은 다음과 같이 들어온다. [ 2 2 0 ], [ 1 3 0 ]
   이런 배열이 입력으로 들어올 때 누적합을 만들면 [ 2 4 4 ], [ 1 4 4 ] 가 된다.
   1 증가가 끝나는 위치와 2 증가가 끝나는 위치가 같다면 2를 증가시키지 않는다.
   
   
4. 1과 2가 0개가 아닐 때 : [ 0 3 3 ], [ 1 2 3 ] 과 같은 입력이 들어온다.
   이전에 1을 증가시켰기 때문에, 2를 증가시킬 때는 1이 끝나는 위치에 1을 증가시켜 이전에 증가시킨 1 + 1이 끝나는 위치에서 증가시킨 1 로 2 증가를 만들어 낸다.
   
   
5. 2는 0개가 아닌데 1이 0개일 때 : 2도 동시에 0개라면 아무것도 증가하지 않지만, 2는 0개가 아닌데 1이 0개라면 4번 케이스와는 다르게 1이 끝나는 위치에서 1을 증가시키는 것보단 2를 바로 증가시켜주어야 한다.

order[day][1] += order[day][0]
order[day][2] += order[day][1]

if order[day][0] != order[day][1]: # 만약 1이 있다면 0 증가가 끝나는 위치와 같지 않을 것임.
    # 1이 있다면 0 증가가 끝나는 위치 (order[day][0]) 부터 1이 추가됨. (누적)
    edge_plus[order[day][0]] += 1
if order[day][1] != order[day][2]: # 만약 2가 있다면 1 증가가 끝나는 위치와 같지 않을 것.
    if order[day][0] == order[day][1]:
        # 1이 없다면 0 증가가 끝나는 위치 (order[day][0]) 부터 2가 추가됨. (누적)
        edge_plus[order[day][0]] += 2 
    else:
        # 1이 있다면 1 증가가 끝나는 위치 (order[day][1]) 부터 1이 추가됨. (누적)
        # 남은 1은 이미 앞에서 +1 증가할 때 누적해서 증가시켰다.
        edge_plus[order[day][1]] += 1

 

2. 내부 처리

자신의 왼쪽(L), 왼쪽 위(D), 위쪽(U)의 애벌레들이 다 자란 다음, 그 날 가장 많이 자란 애벌레가 자란 만큼 자신도 자란다.

이는 가장 많은 증가량을 따른다는 것인데, 가장자리 모양을 잘 관찰해보면 0을 거쳐 1과 2가 증가되는 마지막 구간은 뒷 부분. 즉 제일 위쪽 행 부분이므로, 위쪽 행이 2 증가가 되었다면 내부도 동시에 2가 증가되고, 위쪽 행이 1 증가가 되었다면 내부도 동시에 1이 증가된다. -> 가장자리 배열의 n + 1 번째 요소부터 2 x n - 1 번째 요소까지는 내부와 동일하다.

// Input
4 3
6 0 1
5 2 0
2 5 0

 

2	2	3	5
2	2  ( ↑ )	3  ( ↑ )	5  ( ↑ )
1	2  ( ↑ )	3  ( ↑ )	5  ( ↑ )
1	2  ( ↑ )	3  ( ↑ )	5  ( ↑ )

 

전체 코드

import sys
input = sys.stdin.readline

n, m = map(int, input().rstrip().split())
order = [list(map(int, input().rstrip().split())) for _ in range(m)]

edge_plus = [0 for _ in range(2*n-1)]

for day in range(m):
    # 누적 합 구하기
    # ex. 1 1 2 라면
    #     1 2 4 를 만듬.
    #     - 1 : 0 증가가 끝나는 위치 
    #     - 2 : 1 증가가 끝나는 위치
    #     - 4 : 2 증가가 끝나는 위치 (N)

    order[day][1] += order[day][0]
    order[day][2] += order[day][1]

    if order[day][0] != order[day][1]: # 만약 1이 있다면 0 증가가 끝나는 위치와 같지 않을 것임.
        # 1이 있다면 0 증가가 끝나는 위치 (order[day][0]) 부터 1이 추가됨. (누적)
        edge_plus[order[day][0]] += 1
    if order[day][1] != order[day][2]: # 만약 2가 있다면 1 증가가 끝나는 위치와 같지 않을 것.
        if order[day][0] == order[day][1]:
            # 1이 없다면 0 증가가 끝나는 위치 (order[day][0]) 부터 2가 추가됨. (누적)
            edge_plus[order[day][0]] += 2 
        else:
            # 1이 있다면 1 증가가 끝나는 위치 (order[day][1]) 부터 1이 추가됨. (누적)
            # 남은 1은 이미 앞에서 +1 증가할 때 누적해서 증가시켰다.
            edge_plus[order[day][1]] += 1

# 누적 edge 제작하기.
for i in range(1, 2*n-1): edge_plus[i] += edge_plus[i-1]
# 초기 1 증가시키기.
for i in range(2*n-1): edge_plus[i] += 1

print(' '.join(map(str, edge_plus[n-1:])))
res = ' '.join(map(str, edge_plus[n:]))
for i in range(n-2, -1, -1):
    print(edge_plus[i], end=' ')
    print(res)