[백준 / BOJ] 2563번 색종이 (Python)

문제 링크 : 2563번: 색종이 (acmicpc.net)

2563번: 색종이

 

🖥️ 시작하며

처음의 우여곡절

본인은 처음에 수학적으로 접근했다. 예시 문제를 간단하게 분석해보니 겹치는 부분이 아래와 같은 규칙을 따랐다.

• 가로축에서, 입력받은 x 값이 더 작은 곳에 +10 을 한 뒤 더 큰 x 값을 뺀다.
  예시에서는 3 + 10 - 5 다.
• 세로축에서도 똑같이 진행한다. 예시에서는 2 + 10 - 7 이다.

그렇게 생각하고 문제를 풀다보니 웬걸, 내가 짠 로직은 인접한 두 리스트만 비교해서 중복된 크기를 구하는데, 아무리 정렬을 한다 해도 계속해서 중복된 부분이 나올 수 있는 가능성이 있는 상황을 걸러낼 수가 없었다.

그러다가 이 카테고리가 ‘2차원 배열’인 것에 중점적으로 다시 생각을 해보니, 너무도 쉬운 방법이 있었다.

아래는 실패한 로직이다.

if __name__ == "__main__":
    N = int(input())
    inputArr = []
    sumDup = 0
    for _ in range(N):
        a, b = map(int, input().split())
        inputArr.append([a, b])

    inputArr.sort(key=lambda x: x[0])

    for i in range(N - 1):
        if inputArr[i + 1][0] - inputArr[i][0] < 10:
            tmpMin = min(inputArr[i][1], inputArr[i + 1][1])
            tmpMax = max(inputArr[i][1], inputArr[i + 1][1])
            sumDup += (inputArr[i][0] + 10 - inputArr[i + 1][0]) * (
                tmpMin + 10 - tmpMax
            )

 

문제 해결

그냥 문제에서 답을 주고 있었다. 가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다.. 이에 따르면 그냥 100 x 100 2차원 배열을 만들고 입력받을 때마다 배열을 1로 채운 후, 1의 개수를 세면 되는 아주 간단한 해결 방법이 있었다.

 

정답 코드

import sys

sys = sys.stdin.readline

if __name__ == "__main__":
    N = int(input())
    resArr = [[0] * 100 for _ in range(100)]

    for _ in range(N):
        x, y = map(int, input().split())

        for i in range(x, x + 10):
            for j in range(y, y + 10):
                resArr[i][j] = 1

    print(sum(sum(row) for row in resArr))

 

소감

이게.. 초등부 문제..? 아무리 알고리즘이 아이디어가 중요하다고 하지만 난 초등학교때 이걸 바로 캐치하고 풀 수 있었을까..?

 

부록

참고문헌

---