[파이썬] 백준 10836 : 여왕벌 (골드4)

[파이썬] 백준 10836 : 여왕벌 (골드4)

10836번: 여왕벌

---

문제

---

풀이

 

방향성 생각

• 스위핑. 계속 배열에 더해주면 시간효율 매우구림. 서브태스크 4 통과 못할확률 높다.

 

전체코드

from collections import defaultdict
import sys
input = lambda : sys.stdin.readline().rstrip()

n,m = map(int,input().split())

info = defaultdict(int)
for _ in range(m):
    a,b,c = list(map(int,input().split()))
    info[a] += 1
    info[a+b] += 1

arr = [1]
for i in range(2*n+1):
    if i in info: arr.append(arr[-1]+info[i])
    else: arr.append(arr[-1])
arr.pop(0)

for i in range(n):
    for j in range(n):
        if j == 0: print(arr[n-(i+1)], end=' ')
        else: print(arr[n+j-1], end=' ')
    print()

• 0이 a개, 1이 b개면 a,a+b에서 성장해야할 수가 1씩 늘어난다. 스위핑으로 풀기
• arr = [1]로 초기화 시키고 배열 추가하기. 추가한 후에 맨 앞 초기값 1 필요없으므로 삭제.
• 규칙같은 경우에는 왼,대각,위 중에서 항상 위쪽이 제일 큰 값을 가지게 된다.
• 왼쪽, 위 테두리를 제외한 값들은 항상 맨 위쪽 행과 값이 같다.

 

이전 코드

import sys
input = lambda : sys.stdin.readline().rstrip()

n,m = map(int,input().split())
arr = [1]*(2*n+1)

for _ in range(m):

    a,b,c = list(map(int,input().split()))
    info = [0]*a + [1]*b + [2]*c
    
    for i in range(a,a+b): arr[i] += 1
    for i in range(a+b,2*n-1): arr[i] += 2

for i in range(n):
    for j in range(n):
        if j == 0: print(arr[n-(i+1)], end=' ')
        else: print(arr[n+j-1], end=' ')
    print()

코멘트

2차원 배열 -> 1차원배열까지 풀어보고나서 생각해보다가 스위핑 생각.

시간 1/5배 좋아짐. 메모리 1/2배