백준 파이썬 코딩테스트 (색종이)

---

백준 2563번 문제

색종이

---

문제

 

---

풀이

1.

우선 이 문제는 수학적으로 베이직하게 접근을 해봐야 할 것 같다.

 

우선 정사각형 즉 가로 세로가 각 10인 100의 넓이로 고정이 되어있으니까, 최대 넓이는 100 x N으로 고정이다.

 

이때, 겹치는 넓이만큼을 제외를 하면 정답이다.

 

일단 첫번째 인풋이 색종이의 갯수이기 때문에 최대치에서, 겹치는 범위를 찾아서 빼면 된다.

 

2차원 배열을 받으니, 각각 의 값에서 즉 i번 반복의 n, m 과 i+1의 n, m 의 뺄샘이 10보다 낮으면 즉 n은 n끼리, m은 m끼리 해서

10보다 낮은경우에 곱셈을 한다. 이를 result에 넣은 후 최대값에서 빼면 될것 같다.

 

 

>>

이렇게 문제를 풀려다보니, 겹치는걸 기준으로 뺀다고 했을때, 한번이상 겹치게 되면 문제가 발생하게된다.

이를 생각 못 했고, 중요한건 한번만 겹친다고 한들 n이 많아지면 많아질수록 너무 오래 걸린다. 왜냐면 겹치는걸 계산하기 위해 각각의 row를 모든 row와 계산을 했어야 했기 때문.

 

 

2.

아예 감이 안잡혀서 gpt의 도움을 받았다.

 

사실 뺄셈이 안되면 덧셈을 하라는게 맞는 수순이었던거 같다만.

 

여기서는 곱셈을 하는것이 아닌, 덧셈을 하였다.

즉 array[i][j]가 범위안에 있다면, 이를 1 로 설정한다.

그러면 겹치는 곳또한 결국 1로 될것이고, 이를 for문으로 모든 범위에서 1인  array[i][j]를 카운팅 하면

넓이가 나오게 될 것이다.

 

즉 array[i][j]를 포함 = 넓이 1x1, 미포함이면 0 으로 하는 것이다.

 

정리해보자면, array[i][j]가 0인경우, 범위에 포함된다면 이를 1 로 바꾸고 결과값에 +=1을 한다.

 

이때 기본을 0 으로 해야하기 때문에, array를 100x100으로 값이 0 인 2차원 배열을 생성해야한다.

 

그렇다면 i와 j가 인풋만큼 돌아가는 사이에 모든 범위는 1이 되고, 덮여도 1이다. 이때 0에서 1 이된 경우에만 결과값에 +1을 하면된다.

 

---

결과

import sys
num = int(sys.stdin.readline().strip())

result = 0
array = [[0]*100 for _ in range(100)]

for _ in range(num):
    n, m = map(int, sys.stdin.readline().strip().split())
    for i in range(n, n+10):
        for j in range(m, m+10):
            if array[i][j] == 0:
                array[i][j] = 1
                result += 1

print(result)

 

 

문제를 생각하면서 풀고 블로그에 적고 하다보니 매개변수 명에 대해서 위와 아래를 다르게 설정하는 문제가 가끔 일어난다.

 

문제를 옳게 풀더라고, 매개변수가 다르면 결국 이는 틀린것이다.

 

문제를 풀때, 문제자체와 작성 후에도 검토하는것을 잊지 말아야 겠다.

 

 

 

Coding_Test/백준/Silver/2563. 색종이 at main · K-MarkLee/Coding_Test · GitHub

Coding_Test/백준/Silver/2563. 색종이 at main · K-MarkLee/Coding_Test