문제
가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 색종이의 변과 도화지의 변이 평행하도록 붙인다. 이러한 방식으로 색종이를 한 장 또는 여러 장 붙인 후 색종이가 붙은 검은 영역의 넓이를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 색종이의 수가 주어진다. 이어 둘째 줄부터 한 줄에 하나씩 색종이를 붙인 위치가 주어진다. 색종이를 붙인 위치는 두 개의 자연수로 주어지는데 첫 번째 자연수는 색종이의 왼쪽 변과 도화지의 왼쪽 변 사이의 거리이고, 두 번째 자연수는 색종이의 아래쪽 변과 도화지의 아래쪽 변 사이의 거리이다. 색종이의 수는 100 이하이며, 색종이가 도화지 밖으로 나가는 경우는 없다
출력
첫째 줄에 색종이가 붙은 검은 영역의 넓이를 출력한다.
풀이
내가 생각한 알고리즘
- 가로 세로를 구해서 겹친만큼 나중에 빼주면 된다고 생각했다
-> 반례 O
3
1 1
1 1
1 1어떻게 극복할 것인가?
입력 받은 값에 대해서 겹치는 것을 생각하지 못했다.
중복을 허용한 리스트에서 중복을 허용하지 않은 리스트 즉, Set으로 변환한 뒤 내가 구현한 알고리즘을 쓰면 될거 같다.
근데 그러기에는 또 많은 불필요한 변환이 있을 것으로 판단되어 알고리즘을 수정했다.
- 사용자로부터 정사각형의 개수를 입력받습니다.
- 각 정사각형의 왼쪽 상단 좌표를 입력받고, 해당 좌표부터 우측으로 10개, 아래로 10개의 정사각형을 1로 채웁니다.
- 겹치는 정사각형을 중복하여 세지 않기 위해, 이미 1로 채워진 정사각형에 대해서는 무시합니다.
- 모든 정사각형을 처리한 후, 1로 채워진 정사각형의 개수를 출력합니다.
이 알고리즘은 입력된 정사각형의 좌표를 기반으로 2차원 배열을 만들고, 각 정사각형의 영역을 1로 채워나가는 방식으로 작동합니다. 겹치는 부분을 중복하여 세지 않는다는 점이 주요 특징입니다.
코드
cnt = int(input())
square = []
table = [[0] * 100 for _ in range(100)]
count_num = 0
for i in range(cnt):
a, b = input().split()
a = int(a)
b = int(b)
for one in range(a, a+10):
for two in range(b, b+10):
if table[one][two] == 0:
table[one][two] = 1
count_num +=1
print(count_num)
평가:
1. 시간 복잡도: 이 알고리즘의 시간 복잡도는 입력된 정사각형의 개수에 비례합니다. 입력된 정사각형의 개수를 N이라고 할 때, 2중 반복문을 사용하여 각 정사각형을 확인하므로 O(N)의 시간 복잡도를 갖습니다.
2. 공간 복잡도: 이 알고리즘의 공간 복잡도는 2차원 배열의 크기에 비례합니다. 2차원 배열의 크기는 고정되어 있으므로 O(1)입니다.
이 알고리즘은 주어진 문제를 효과적으로 해결하는 데 있어서 효율적인 접근 방식을 취하고 있습니다. 겹치는 정사각형을 중복해서 세지 않고, 배열을 효율적으로 사용하여 각 정사각형을 채우는 방식으로 동작합니다. 이러한 특징은 알고리즘의 시간 복잡도와 공간 복잡도를 효율적으로 관리하고 있음을 보여줍니다.
Lesson Learn
table = [[0] * 100 for _ in range(100)]
x, y = map(int, input().split()) # 색종이의 왼쪽 상단 좌표
- 0으로 초기화된 100 100 배열을 선언하는 것
- int로 맵핑하는 것
