[백준 BOJ] 2563번(색종이) Python 풀이

# 해당 포스팅은 이제 막 알고리즘 공부를 시작한 초보 수준에서 작성했음을 이해해주시고, 비난보다는 따뜻한 조언을 부탁드립니다.

---

안녕하십니까, 간토끼입니다.

오늘은 백준 2563번 (색종이)에 대해 다뤄보겠습니다.

1. 문제 링크

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

2563번: 색종이

가로, 세로의 크기가 100인 100x100 정사각형인 도화지에 가로, 세로의 크기가 각각 10인 정사각형 모양의 색종이를 겹쳐서 도화지 위에 올릴 수 있다고 하면, 겹쳐진 색종이들의 넓이를 구하는 문제입니다.

색종이를 붙인 위치는 두 개의 자연수로 주어집니다. 첫 번째 자연수는 색종이의 왼쪽 변과 도화지의 왼쪽 변 사이의 거리라고 돼있으니, 이를 x라고 합시다.

그리고 두 번째 자연수는 색종이의 아래쪽 변과 도화지의 아래쪽 변 사이의 거리니, 이를 y라고 합시다.

즉 정사각형 도화지를 2차원 좌표 평면이라고 한다면,  주어진 자연수 x,y는 색종이의 좌표(x,y)가 되겠네요.

그러므로 2차원 배열을 구현해주면 됩니다. 다만 몇 가지 요소를 고려해야 할 필요가 있겠죠.

 

2. 접근 방법

다음과 같이 접근하였습니다.

몬테칼로 적분법이라고 하는데요. 어떤 함수의 특정 구간에서의 넓이를 구하고 싶다면, 일정한 개수의 점을 균일하게 분포시켜서 해당 함수 이내에 점이 몇개 찍혀있는지를 파악하여 근사적으로 넓이를 구하는 방법입니다.

그냥 거창하게 표현하면 이렇고, 아이디어만 빌려봅시다.

먼저 100x100 정사각형 도화지를 만들기 위해 0이 찍혀있는 100x100 list인 map_array를 정의합니다.

이후 입력된 색종이에 해당하는 좌표에 1을 찍어줍니다.

그러면 색종이들의 입력이 종료되면 map_array는 0과 1로 이루어져 있겠죠.

이때 1인 원소들의 합을 구해준다면 그게 넓이가 됩니다.

이러한 아이디어를 활용해주었습니다.

 

3. 코드

# 백준 : 2563 색종이
# 풀이방법 : 몬테칼로 적분법 이용

# 입력 : 색종이 수
n = int(input())
map_array = [[0]*100 for _ in range(100)] # 100x100 도화지 만들기

for _ in range(n):
    x, y = map(int, input().split())
    # x : x ~ x+10
    # y : y ~ y+10
    for i in range(y, y+10):
        idx_y = i
        # i,j에 해당하는 좌표에 점을 찍음
        for j in range(x, x+10):
            idx_x = j
            if map_array[idx_y][idx_x] == 0:
                map_array[idx_y][idx_x] = 1
            else:
                pass
            
sum_array = 0
for i in range(100):
    sum_array += sum(map_array[i])
print(sum_array)

 

감사합니다.

잘 읽으셨다면 게시글 하단에 ♡(좋아요) 눌러주시면 감사하겠습니다 :)

(구독이면 더욱 좋습니다 ^_^)

* 본 블로그는 학부생이 운영하는 블로그입니다.

따라서 포스팅에 학문적 오류가 있을 수 있으며, 이를 감안해서 봐주시면 감사하겠습니다.

 

---

- 간토끼(DataLabbit)

- B.A. in Economics, Data Science at University of Seoul