[파이썬] 백준 2563번 「색종이」

문제

백준 2563번/실버5

 

 

문제 해석

100 * 100 큰 도화지 안에 10*10 색종이를 여러 개 붙였을 때, 색종이가 붙은 영역의 넓이를 구하는 문제이다.

단 고려해야하는 것은, 색종이를 겹치게 붙였을 경우에는 영역의 넓이는 "10*10 + 10* 10  - 겹치는 범위" 라는 것을 인지하여야한다. 문제 조건으로는 색종이의 왼쪽아래 꼭짓점의 위치가 주어지므로, 이를 이용하여 계산하여야한다.

 

 

 

풀이 전략

문제조건에서는 색종이의 왼쪽아래 꼭짓점의 위치를 주어진다. "10*10 + 10* 10  - 겹치는 범위"를 일일이 계산하기는 귀찮으니까, 그냥 100*100 배열을 생성하고, 색종이의 시작점에 따라 색종이의 영역에 10*10 크기만큼 영역을 표시해주는 방식으로 해보자.

문제 조건에서 색종이는 100개가 되지 않음 / 도화지의 넓이는 100*100 = 10000이고 라고 하였으므로, 최대 계산횟수는 100*100*100 = 1000000, 즉 백만밖에 되지 않는다. 한 천만 정도로 넘어가게 되면 시간초과가 뜨지만 이곳은 삼중포문을 써도 백만밖에 되지 않기에 충분히 사용할 만 하다. 그래서 삼중포문을 사용하겠다.

 

처음에 도화지의 넓이에 해당하는 2차원 배열을 생성한다. 다만, 파이썬에서는 인덱스가 0부터 시작하므로 계산하기 쉽게 하기 위해서 (100+1) * (100+1) 의 범위로 생성을 해준다.

그 다음 입력받은 꼭짓점 시작점으로부터 x + 10 , y +10 에 해당하는 영역을 True로 바꿔준다.

이를 테스트 케이스 만큼 반복하고, True로 표시된 영역의 개수는 몇 개인가 세주기만 하면 원하는 답을 구할 수 있다.

 

 

 

코드

import sys;

max_range = 100; #도화지 최대 범위
    

#계산을 편하게 하기 위해 max_range 보다 1개 더 큰 2차원 배열 생성
maze = [[False for _ in range(max_range+1)] for _ in range(max_range+1)]  #색종이 영역을 표시위한 변수

n = int(sys.stdin.readline().rstrip()); #n 입력

#테스트케이스 n만큼 반복
for _ in range(n):
    x, y = map(int, sys.stdin.readline().split()); #x, y 시작점 입력
    
    for i in range(x, x+10): #x축 10개 영역
        for j in range(y, y+10): #y축 10개영역
            maze[i][j] = True; #색종이가 붙었다는 것을 표시
    
count= 0; #True(영역 표시)된 곳 세기 위한 변수
for i in range(1, max_range+1):
    for j in range(1, max_range+1):
        if maze[i][j] == True: # 색종이가 붙은 곳 확인
            count+=1; #개수 세기
            
print(count);

 

 

 

결과

 

 

 

고찰

기계학습개론할 때 넘파이 쓰면 maze[x:x+10, y:y+10] = True 이런식으로 슬라이싱이 가능하였는데, 일반 파이썬에서는 안 되는 것 같다. 솔직히 저 때 이중포문 더 쓰기 귀찮아서 슬라이싱으로 해결하려 했는데, 잘 해결되지 않았다.