3 분 소요

문제

가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 색종이의 변과 도화지의 변이 평행하도록 붙인다. 이러한 방식으로 색종이를 한 장 또는 여러 장 붙인 후 색종이가 붙은 검은 영역의 넓이를 구하는 프로그램을 작성하시오.

예를 들어 흰색 도화지 위에 세 장의 검은색 색종이를 그림과 같은 모양으로 붙였다면 검은색 영역의 넓이는 260이 된다.

입력

첫째 줄에 색종이의 수가 주어진다. 이어 둘째 줄부터 한 줄에 하나씩 색종이를 붙인 위치가 주어진다. 색종이를 붙인 위치는 두 개의 자연수로 주어지는데 첫 번째 자연수는 색종이의 왼쪽 변과 도화지의 왼쪽 변 사이의 거리이고, 두 번째 자연수는 색종이의 아래쪽 변과 도화지의 아래쪽 변 사이의 거리이다. 색종이의 수는 100 이하이며, 색종이가 도화지 밖으로 나가는 경우는 없다

출력

첫째 줄에 색종이가 붙은 검은 영역의 넓이를 출력한다.

예제 입력 1 복사

3 3 7 15 7 5 2

예제 출력 1 복사

260

스스로 고민

  • 구현하는 부분이 확실히 어렵다.
  • 색종이의 넓이는 무조건 100이므로 겹쳐지는 부분을 어떻게 측정할 수 있을지 고민을 많이 했다.
  • 예제에서 색종이가 3장이면 총 넓이는 300이고 거기서 겹쳐지는지 체크 그리고 겹쳐지는 부분을 뺴면되는데 이 부분을 어떻게 하면 해결 할 수 있을까?
  • 우선 좌표를 받고 겹쳐지는지 체크
  • 겹쳐진다면 총 합에서 넓이 제거
  • 근데 몇 장이 겹쳐지는지 또한 생각을 해봐야 한다.
  • 리스트에 좌표를 넣는다.
  • 처음 색종이의 좌표가 3,7 일 경우 가로는 3~13 세로는 7~17
  • 두 번째 색종이는 5~15, 세로는 2~12
  • 가로는 8cm 세로는 5cm 가 겹쳐진다
  • 총 40cm 가 1개 겹치므로 300 - 40 = 260
  • 근데 3장 4장 이렇게 겹쳐질 경우만 확인 할 수 있으면 될 것 같았다.

구현 코드

import sys

n = int(sys.stdin.readline().strip())
answer = n * 100
paper_list = []

for _ in range(n):
    coordinate = list(map(int, sys.stdin.readline().split()))
    if len(paper_list) < 1:
        paper_list.append(coordinate)
    
    else:
        for i in paper_list:
            if abs(i[0] - coordinate[0]) < 10 and abs(i[1] - coordinate[1]) < 10:
                answer -= (10-abs(i[0]-coordinate[0])) * (10-abs(i[1]-coordinate[1]))
                
print(answer)
  • 당연히 문제가 틀렸는데 곰곰히 생각해보니 첫 번째 두 번째 세 번째 모두 동시에 겹쳐지지만 겹쳐지는 부위가 또 다른 경우에 지금 코드는 문제가 있다고 생각했다.
  • 수식으로는 좋은 방법이 생각나지 않아서 답을 보고 풀었다.
N = int(input())
array = [[0] * 100 for _ in range(100)]  # 도화지 범위 초기화
for _ in range(N):  # 입력 받은 도화지 개수만큼 돈다.
    y1, x1 = map(int, input().split())  # 왼쪽아래 x,y 좌표를 받는다.

    for i in range(x1, x1 + 10):  # 세로를 돈다.
        for j in range(y1, y1 + 10):  # 가로를 돈다.
            array[i][j] = 1  # 해당 범위 값을 0에서 1로 바꿔준다.

result = 0  # 넓이를 출력할 변수
for k in range(100):  # 전체 도화지를 돌면서
    result += array[k].count(1)  # 1 개수만 세어준다

print(result)
  • 구현을 아예 그냥 해당 좌표를 1로 표시한 후 1만 카운트하는 방식으로 문제를 풀어냈다.

    시간 복잡도와 공간 복잡도

시간 복잡도:

  1. N을 입력받는 부분의 시간 복잡도는 O(1)다.
  2. 이중 반복문을 사용하여 도화지에 사각형을 표시하는 부분의 시간 복잡도는 O(N)다. 이중 반복문 내에서 상수 번의 연산만 수행되기 때문에 상대적으로 N에 비해 무시할 만한 시간이 소요된다.
  3. 전체 도화지를 검사하여 1의 개수를 세는 부분의 시간 복잡도는 O(100)다.

따라서 전체 코드의 시간 복잡도는 O(N) 다.

공간 복잡도:

  1. array는 100x100 크기의 2D 배열로, 고정된 크기를 갖기 때문에 공간 복잡도는 O(10000) 또는 O(1)다.
  2. 나머지 변수들은 상수 개수의 변수이므로 추가적인 공간을 차지하지 않으므로 공간 복잡도 역시 O(1)다.

따라서 전체 코드의 공간 복잡도도 O(1) 다.

회고 과정

  • 정말 문제를 단순하게 만들어서 단순 계산만 컴퓨터한테 시키는 사고력 연습을 해야겠다.
  • 그냥 0으로 모든 좌표를 만든 뒤 입력 받은 좌표에서 주어진 정사각형 만큼의 크기만큼 1로 채워서 문제를 간단하게 해결할 수 있는 문제였는데 너무 복잡하게 생각했다.
  • 혹시나 나랑 비슷하게 접근해서 풀어본 방식이 있나 찾아봤지만 대부분 1로 채워서 문제를 해결하는 방식이였는데 이러한 유형의 문제는 이렇게 푸는 방향으로 외우는게 맞는건지
  • 아니면 창의적으로 푸는게 맞는건지 좀 헷갈렸다.
  • 앞으로 이러한 유형의 문제는 지금 방법처럼 사고하는 방법을 떠올리고 해당 문제도 다시 풀어볼 문제에 저장…

댓글남기기

참고