https://www.acmicpc.net/problem/2563
문제
가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 색종이의 변과 도화지의 변이 평행하도록 붙인다. 이러한 방식으로 색종이를 한 장 또는 여러 장 붙인 후 색종이가 붙은 검은 영역의 넓이를 구하는 프로그램을 작성하시오.
예를 들어 흰색 도화지 위에 세 장의 검은색 색종이를 그림과 같은 모양으로 붙였다면 검은색 영역의 넓이는 260이 된다.
입력
첫째 줄에 색종이의 수가 주어진다. 이어 둘째 줄부터 한 줄에 하나씩 색종이를 붙인 위치가 주어진다. 색종이를 붙인 위치는 두 개의 자연수로 주어지는데 첫 번째 자연수는 색종이의 왼쪽 변과 도화지의 왼쪽 변 사이의 거리이고, 두 번째 자연수는 색종이의 아래쪽 변과 도화지의 아래쪽 변 사이의 거리이다. 색종이의 수는 100 이하이며, 색종이가 도화지 밖으로 나가는 경우는 없다
출력
첫째 줄에 색종이가 붙은 검은 영역의 넓이를 출력한다.
예제 입출력
이것도 초등부 문제다.
풀이 1 (정답)
mat = [[0 for col in range(100)] for row in range(100)] # 100x100짜리 행렬 만들고 0으로 초기화
result = 0
for _ in range(int(input())): # 좌표 입력
x, y = map(int, input().split())
for row in range(x, x+10): # 해당 x, y좌표부터 +10만큼
for col in range(y, y+10):
mat[row][col] = 1 # 1로 채움
for row in range(100): # 모든 행렬 값에 접근해
for col in range(100):
result += mat[row][col] # 1들의 합을 구함
print(result)아이디어를 떠올리기 위해 2차원 수직선을 그려봤는데,
생각해보니 x, y축 모두 0~100의 범위를 가지고, 간격이 유리수가 아닌 정수 단위이므로
100*100짜리 표를 검은색으로 칠하는 것과 같다고 생각했다.
그렇게 떠올리니 구현은 어렵지 않았다.
생각보다 금방 풀었다.
풀이 2 (정답)
mat = [[0 for col in range(100)] for row in range(100)]
result = 0
for _ in range(int(input())):
x, y = map(int, input().split())
for row in range(x, x+10):
for col in range(y, y+10):
mat[row][col] = 1
for i in mat:
result += sum(i)
print(result)풀이 1에서 1의 합(=사각형의 넓이)을 구하는 부분만 바꿔보았다.
for문의 개수가 하나 줄어서 좀 더 빠를 줄 알았는데 그렇진 않았다.
풀이 3 (정답, 파이리썬님 코드 일부 참고)
mat = [[0 for col in range(100)] for row in range(100)]
result = 0
for _ in range(int(input())):
x, y = map(int, input().split())
for row in range(x, x+10):
for col in range(y, y+10):
mat[row][col] = 1
for row in mat:
result += row.count(1)
print(result)이번에도 풀이 1의 코드에서 넓이 구하는 부분만 바꿔보았다.
1의 합이 아닌 1의 개수를 구해보았는데, 실행 시간에는 큰 차이가 없었다.
