백준) 색종이

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

이 문제를 처음 봤을때에는 수학 공식을 대입 하여 코드가 길어지 않을까? 라는 생각이 먼저 들었다.

 

그러나 지금까지 들었던 강의와 스쿼드를 진행하면서 배워왔던 지식이 떠올랐다.

 

DFS, BFS, 스택, 큐 등등 과연 이중에 이걸 간단히 해결 할게 있을까...

 

그러다 DP, 동적 프로그래밍이 떠올랐다. 간단히 생각해서 주어진 도화지 안에 임의 정사각형 짜리 색종이를 붙이는 거다. 붙이는건 누구나 할 수 있지만 곁침 부분을 생각해야 되는데 이럴때 그냥 도화지 전체를 '0'으로 초기화 하고 색종이가 붙은 자리를 '1'로 변경한 뒤 전체를 계산하면 간단히 끝난다.

dp = [[0 for j in range(100)] for i in range(100)]
T = int(input())
for _ in range(T):
    x, y = map(int, input().split())
    for i in range(x, x+10):
        for j in range(y, y + 10):
            dp[i][j] = 1
print(sum(sum(dp,[])))

 

만약에 내가 DP 를 모르는 상태였다고 하면 색종이가 주워질 때마다 그 시작점과 끝점을 계산 찾아 저장 한 뒤 입력이 끝난 뒤에 다시 반복문을 실행하여 곁침을 찾아 제외하는 작업을 했을것이다.

 

이렇게 되면 코드가 길어 질 뿐만 아니라 나중에 코드를 보아도 이해하기 어려운 코드가 탄생하지 않을까라는 생각이 든다.

 

오늘은 배워왔던 지식을 활용했다는 점에 조금은 뿌듯한 기분인다.