답:
import sys
def area(): #input 으로 받으니까 넣지 않아도 됨
inp = int(sys.stdin.readline())
paper = [[0]*100 for i in range(100)]
for _ in range(inp):
width, length = map(int, input().split())
#주어진 w, l 에서 10만큼씩 채워주기
for w in range(width, width+10):
for l in range(length, length+10):
paper[w][l] = 1
result = 0
for row in paper:
result += sum(row)
return result
print(area())
문제 분석 및 해석
- 문제 -
가로세로 100 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이 붙이기
색종이의 변과 도화지의 변이 평행하도록 붙이는데, 색종이를 한 장 또는 여러 장 붙인 후 색종이가 붙은 검은 영역의 넓이를 구하는 프로그램을 작성한다 (색종이의 부분이 겹칠 수 있음!)
<입력값>
색종이 숫자를 1번째 줄
색종이 붙인 위치 2 3 4. ..
<입력>
3
3 7
15 7
5 2
1) 생각한 풀이
가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이
검은 색종이의 개수별 너비를 구하기,
주어지는 숫자로 2개씩 대조해
도화지가 겹치는 부분을 검사,
크기를 구해 빼주기
** 아주 여러개가 겹칠수도 있다..!
혹은 남는 부분을 더해서 100*100에서 빼주기?
이게 더 간단할수도 있을 것 같다!
=> 이방법들은 풀이가 너무 복잡하고, 코드로 구현하기 어려움
2) 풀이 찾기...
참고한 블로그들 :
스위핑 + 관련문제들
https://lubiksss.github.io/boj/BOJ_Sweeping/
여러 직사각형의 넓이 구하기, 백준: 2669
스위핑 + 선긋기, 백준: 2170
https://byeo.tistory.com/entry/%EC%8A%A4%EC%9C%84%ED%95%91-Sweeping
스위핑 sweeping
스위핑sweeping은 "쓸다"를 의미한다
스위핑 알고리즘 이란 말 그대로 한 쪽 방향부터 시작해서 다른 방향으로 스캔해가면서 쓸어가는 것!
이 알고리즘은 특정한 자료구조나 구체적인 코드가 있는 것은 아니며, 단지, 한쪽 방향에서 시작해서 다른 방향으로 차근차근 해결해 나가는 기법을 칭하는 말이다. 보통 좌표와 관련있는 문제에서 자주 활용됨
풀이를 보고, + 네비게이터의 도움을 받아 작성한 풀이
- 0으로 이차원 배열만들기
- 길이는 100 * 100
- 검은 사각형이 위치한 곳이 1로 표현될 수 있도록 하기
겹치는 부분은 하나의 영역으로 구할 수 있게.
+++
블로그들을 참고하며 클론코딩으로 완성하였다.
추가로 '겹치는 선분의 길이'를 풀어보며 오늘 배운 것을 복습해야겠다.
과정1.
입력 값을 받기 위한 readline을 넣어 변수를 정의
100 * 100 의 이차원 배열을 만들었다.
+ [0] * 100 을 하면 list요소가 100개 곱해진 리스트가 만들어짐!!
import sys
def area(): #input 으로 받으니까 넣지 않아도 됨
inp = int(sys.stdin.readline())
paper = [[0]*100 for i in range(100)]
# input = sys.stdin.readline
# white_list = [[0 for _ in range(input) for _ in range(input)]]
# 처음에 input값이 100이라고 착각했다^^; 문제를 잘 읽자
# 게다가 for문을 2번사용하면 시간복잡도가 올라가므로 위 paper 변수처럼 작성하기를 추천받았다
과정2.
검은 정사각형이 10 * 10이라는 것을 알고 있으므로
range로 input 받은 숫자 width, length의 범위를 만들어준다.
그리고 paper에 각각의 index를 넣어주어 1로 바꾸어주도록 한다.
for _ in range(inp):
width, length = map(int, input().split()) # 예시 '3 7', 위치를 표현하는 2개의 숫자 받아주기
#주어진 w, l 에서 10만큼씩 채워주기
for w in range(width, width+10):
for l in range(length, length+10):
paper[w][l] = 1
paper[w][l] = 1
클론코딩을 하며 이부분이 이해가 잘 가지 않아 차근차근 생각해보았는데
위에서 for 문 range로 width와 length를 각각 돌려주고 있으므로 범위 내의 모든 위치가 들어가게 되는 것이었다.
예를들어 width = 1, length = 5 라면
width는 1 ~11, length는 5 ~ 15를 각각 넣어주고 있어
범위 내 모든 위치를 참조하게 되는것!
과정3.
result = 0
for row in paper:
result += sum(row)
그리고 paper내에서 1로 변경해준 것을 모두 찾아 더해주면 결과 출력!
+++
input() readline()으로 함수를 받을 때는 함수에 인자를 넣어주지 않아도 괜찮다
함수가 동작하도록 불러오기만 해주면 된다.
>>> area()
>>> print(area())
함수 내의 반환 값 return 을 출력하기 위해서는 print()로 감싸주어야 하는 것!
느낀점:
오늘은 각자가 골라온 문제를 풀기로 했는데, 첫 문제부터 눈이 핑핑 돌아가서 당황스러웠다..ㅠㅠ
한 번 풀어보며 풀이를 알게되었으니 앞으로 비슷한 문제를 만나도 당황하지 않을 수 있지 않을까!
그리고 팀원들 덕에 return, print의 용법을 짚어 볼 수 있었다^^!
매일매일이 새로워서 꾸준한 풀이의 중요성을 느낀다..
'알고리즘 풀이' 카테고리의 다른 글
| [algorithm] 페어 - 백준:2108 통계학 (1) | 2023.05.04 |
|---|---|
| [algorithm] 페어 - 백준:25314 코딩은 체육과목 | 프로그래머스: 문자열 내 마음대로 정렬하기 (0) | 2023.05.03 |
| [algorithm] 페어 - 프로그래머스: 나머지가 1인 수, 없는 숫자 더하기 (0) | 2023.05.01 |
| [algorithm] 페어 - 프로그래머스: 비밀지도 (0) | 2023.04.28 |
| [algorithm] 페어 - 백준: 25304 영수증 (0) | 2023.04.27 |