[백준-파이썬] python, 2563번 색종이 (실버5)

 

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

2563번: 색종이

 

처음에 이 문제를 접했을 때는 어렵게 생각했어요. 도화지 크기가 100 * 100 이니까 면적을 먼저 구하고 거기서 색종이 면적을 빼고, 다음 색종이의 면적도 빼고, 그럼 첫번째 색종이와 두번째 색종이가 서로 겹치는 면적은 두번 빼는 게 되니까 한번은 다시 더해주고.....

 

몇시간을 생각하다가 포기했었어요.

 

근데 한참 묵혀뒀다가 오늘 이 문제를 다시 열어보니, 문제를 보자마자!! 조금 더 쉬운 방법이 생각났어요!

 

이게 바로 브루잉 효과일까요. ㅋㅋ

 

 

답을 바로 원하시는 분은 아래 '여기'를 클릭하셔서 맨 아래로 곧바로 이동하시면 됩니다!

 

여기

 

---

<풀이 과정>

도화지 크기가 100 x 100 밖에 안되기 때문에 100 x 100짜리 2차배열을 만들면 되겠더군요.

0으로 가득찬 배열요. 

그러니까 가로 100칸 세로 100칸의 모눈종이를 만드는 거예요!

 

그리고 색종이를 붙이는 칸은 우리가 색칠한다고 생각합시다.

색칠은 숫자 1로 하는 거예요.

 

아무리 덧칠(새로운 색종이 덧붙이는 것)을 해도 색칠은 무조건 1.

 

그럼 색종이를 다 붙이고 나서, 숫자 1 이 몇개인지 세면 몇칸이 칠해져있는지 알 수 있죠!

 

 

 

일단 100 x 100 사이즈의 0으로 가득찬 배열부터 만들어볼게요.

 

근데 100 x 100은 너무 커서 결과를 직관적으로 보기 힘드니까 일단 10 x 10 사이즈로 축소해서 만들어볼게요.

 

 

 

1. 도화지 만들기

small_paper = [[0 for _ in range(10)] for _ in range(10)]

print(small_paper)

위 코드를 실행하면 아래처럼 0으로 가득찬 2차 배열이 생성됩니다.

[
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
]

이렇게 2차배열로 체스판과 같은 구조를 만들 수 있어요.

사실 이렇게 보기 좋게 나오지는 않고, 실제로는 아래처럼 나오지만 알아보기 쉽도록 제가 다듬은 거예요. :)

 

 

 

 

 

 

어쨌든 보기에 덜 직관적이니까, 아래처럼 코드를 수정해서 딱 맞춰 보이도록 할게요.

small_paper = [[0 for _ in range(10)] for _ in range(10)]

for paper in small_paper:
    print(paper, sep="\n")

 

보기가 한결 낫네요.

 

 

 

 

 

 

2. 색종이 붙인 부분 값 바꾸기

숫자 0들을 숫자 1로 변경하고 결과를 확인하려니까 저는 눈이 좀 아팠어요.

그래서 숫자 0을 '-'로 바꾸고 1로 칠하려던 계획은 하트로 바꾸겠습니다.

small_paper = [['-' for _ in range(10)] for _ in range(10)]

small_paper[2][3:6] = "♥" * 3

for paper in small_paper:
    print(paper, sep="\n")

['-', '-', '-', '-', '-', '-', '-', '-', '-', '-']
['-', '-', '-', '-', '-', '-', '-', '-', '-', '-']
['-', '-', '-', '♥', '♥', '♥', '-', '-', '-', '-']
['-', '-', '-', '-', '-', '-', '-', '-', '-', '-']
['-', '-', '-', '-', '-', '-', '-', '-', '-', '-']
['-', '-', '-', '-', '-', '-', '-', '-', '-', '-']
['-', '-', '-', '-', '-', '-', '-', '-', '-', '-']
['-', '-', '-', '-', '-', '-', '-', '-', '-', '-']
['-', '-', '-', '-', '-', '-', '-', '-', '-', '-']
['-', '-', '-', '-', '-', '-', '-', '-', '-', '-']

 

종이를 축소시켰으니까 색종이 크기도 3 x 3으로 축소할게요.

시험삼아 한줄만, 세칸 칠해볼게요.

 

 

small_paper[2][3:6] = "♥" * 3

 

 

위 구문 덕에 small_paper의 [2]번째 행의 [3:6]까지가 하트로 칠해졌습니다.

빼기 기호 3개를 하트로 바꿔야 하므로 "♥" 곱하기 3을 해줍니다.

 

 

곱하기를 안해주면 어떻게 될까요.

 

['-', '-', '-', '-', '-', '-', '-', '-', '-', '-']
['-', '-', '-', '-', '-', '-', '-', '-', '-', '-']
['-', '-', '-', '♥', '-', '-', '-', '-']
['-', '-', '-', '-', '-', '-', '-', '-', '-', '-']
['-', '-', '-', '-', '-', '-', '-', '-', '-', '-']
['-', '-', '-', '-', '-', '-', '-', '-', '-', '-']
['-', '-', '-', '-', '-', '-', '-', '-', '-', '-']
['-', '-', '-', '-', '-', '-', '-', '-', '-', '-']
['-', '-', '-', '-', '-', '-', '-', '-', '-', '-']
['-', '-', '-', '-', '-', '-', '-', '-', '-', '-']

[3:6]까지 하트 하나로 퉁쳐버려서 리스트가 줄어버렸네요.

 

 

 

 

 

이제 맨 위에서 [2]행 부터 [4]행까지 3 x 3 크기로 하트를 채워보겠습니다.

small_paper = [['-' for _ in range(10)] for _ in range(10)]

small_paper[2][3:6] = "♥" * 3
small_paper[3][3:6] = "♥" * 3
small_paper[4][3:6] = "♥" * 3

for paper in small_paper:
    print(paper, sep="\n")

['-', '-', '-', '-', '-', '-', '-', '-', '-', '-']
['-', '-', '-', '-', '-', '-', '-', '-', '-', '-']
['-', '-', '-', '♥', '♥', '♥', '-', '-', '-', '-']
['-', '-', '-', '♥', '♥', '♥', '-', '-', '-', '-']
['-', '-', '-', '♥', '♥', '♥', '-', '-', '-', '-']
['-', '-', '-', '-', '-', '-', '-', '-', '-', '-']
['-', '-', '-', '-', '-', '-', '-', '-', '-', '-']
['-', '-', '-', '-', '-', '-', '-', '-', '-', '-']
['-', '-', '-', '-', '-', '-', '-', '-', '-', '-']
['-', '-', '-', '-', '-', '-', '-', '-', '-', '-']

요 부분은 1씩 증가하면 되니 아래처럼 for 문으로 대체하겠습니다.

 

small_paper = [['-' for _ in range(10)] for _ in range(10)]

for i in range(2, 5):
    small_paper[i][3:6] = "♥" * 3

for paper in small_paper:
    print(paper, sep="\n")

['-', '-', '-', '-', '-', '-', '-', '-', '-', '-']
['-', '-', '-', '-', '-', '-', '-', '-', '-', '-']
['-', '-', '-', '♥', '♥', '♥', '-', '-', '-', '-']
['-', '-', '-', '♥', '♥', '♥', '-', '-', '-', '-']
['-', '-', '-', '♥', '♥', '♥', '-', '-', '-', '-']
['-', '-', '-', '-', '-', '-', '-', '-', '-', '-']
['-', '-', '-', '-', '-', '-', '-', '-', '-', '-']
['-', '-', '-', '-', '-', '-', '-', '-', '-', '-']
['-', '-', '-', '-', '-', '-', '-', '-', '-', '-']
['-', '-', '-', '-', '-', '-', '-', '-', '-', '-']

색종이 한장을 붙인겁니다.

 

 

 

 

 

3. 색종이 위치 값 전달하기

색종이 붙이는 방법은 구현했으니, 이제 어디에 붙일 것인지 위치를 잘 정해줍시다.

 

# 이 코드를
for i in range(2, 5):
    small_paper[i][3:6] = "♥" * 3

# 이렇게 수정
for i in range(y1, y2):
    small_paper[i][x1:x2] = "♥" * 3

 

이렇게 x1, x2, y1, y2 라는 변수로 값을 받게 설정해둡니다. 

 

 

 

문제의 예시를 보면, 좌변으로부터의 거리(x축 값) 3이 먼저 입력되고 밑변으로부터의 거리(y축 값) 7이 나중에 입력됩니다.

 

 

각각 y, x 로 값을 받아옵니다. 

이 값들을 적절한 좌표값으로 변형해서 x1, x2, y1, y2에 넣어주겠습니다.

x, y = map(int, input().split())  # 3, 7이 들어올 예정

small_paper = [['-' for _ in range(10)] for _ in range(10)]

for i in range(y1, y2):
    small_paper[i][x1:x2] = "♥" * 3

for paper in small_paper:
    print(paper, sep="\n")

 

 

사소한 문제가 하나 있습니다.

보통 그래프는 그림처럼 y축 값 0이 맨아래에 위치하지만

 

 

 

우리가 리스트로 만든 모눈종이는 리스트 특성상 y축 값 0이 맨 위에 위치한다는 점입니다. 그림처럼요.

리스트는 이런 구조니까요.

[
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]   <- arr[0]
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]   <- arr[1]
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]   <- arr[2]
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]   <- arr[3]
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]   <- arr[4]
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]   <- arr[5]
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]   <- arr[6]
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]   <- arr[7]
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]   <- arr[8]
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]   <- arr[9]
]

 

 

 

그래서 우린 네모칸을 칠하기 위해 아래와 같이 좌표값들을 구해야 합니다.

 

 

색종이의 가로와 세로는 동일하게 3이니까 painting = 3이라고 변수에 할당해놓겠습니다.

 

x, y 값으로 3, 5가 들어왔다고 치면,

painting = 3    # 색종이의 가로와 세로 크기

x1 = x
x2 = x + painting

y1 = len(small_paper) - y - painting
y2 = len(small_paper) - y

x1 = 3

x2 = 3+3 = 6

 

y1 = 10 - 5 - 3 = 2

y2 = 10 - 5 = 5

 

x축으로는 3,4,5

y축으로는 2,3,4

이렇게 칠하게 되겠네요.

 

 

 

이렇게 수정합니다.

x, y = map(int, input().split())  # 3, 7이 들어올 예정

small_paper = [['-' for _ in range(10)] for _ in range(10)]

painting = 3

x1 = x
x2 = x + painting

y1 = len(small_paper) - y - painting
y2 = len(small_paper) - y


for i in range(y1, y2):
    small_paper[i][x1:x2] = "♥" * painting

for paper in small_paper:
    print(paper, sep="\n")

 

 

 

 

 

4. 마무리

거의 다 왔습니다.

이제 문제의 본래 조건인 100 x 100 짜리 큰 도화지로 바꿔주고, 빼기 기호와 하트 대신 숫자 0과 1로 채워주겠습니다.

 

색종이 크기도 10 x 10 이므로 아래처럼 변경해줍니다.

 

painting = 10

 

 

그리고 첫째 줄에는 색종이 수가 주어진다고 했으니 그만큼 반복하도록 처리를 해봅니다.

 

small_paper는 더이상 small이 아니니 big_paper로 바꿔줄게요. 

 

 

완성된 답

case = int(input())
big_paper = [[0 for _ in range(100)] for _ in range(100)]
painting = 10
    
for _ in range(case):
    x, y = map(int, input().split())  

    x1 = x
    x2 = x + painting

    y1 = len(big_paper) - y - painting
    y2 = len(big_paper) - y

    for i in range(y1, y2):
        big_paper[i][x1:x2] = [1] * painting

result = 0

for lines in big_paper:
    result += lines.count(1)
    
print(result)

 

하트 대신 [1] 로 변경해 준 것은,

하트는  small_paper[i][x1:x2] = "♥" * painting  이렇게 표시했었지만

숫자 1은 곱하기 하는 순간 연산이 되어버리기 때문에 [1] * painting의 형태로 넣어줍니다.

 

끝났습니다.    :)