1780번 종이의 개수

문제 출처 : https://www.acmicpc.net/problem/1780

사고과정

Divide and Conquer를 배우며 분할정복의 가장 대표적인 예제를 풀었다. 교수님께서 말씀하신 바, 분할정복의 Design은

1. Divide problem to subproblems( >=2 )
2. Counquer(Solve) subproblem
3. Combine subproblems

만약 현재 사각형이 모두 같은 값으로 이루어져 있지 않다면 Divide.

Divide한 작은 사각형(=subproblem)의 값들을 조사해서 만약 모두 같은 값이라면 Conquer( 해당 subproblem ) 해결. 만약 모두 같은 값이 아니라면 다시 recursive하게 Divide.
더 이상 Divide할 수 없다면 이것 또한 Conquer.

이 문제에서는 Optional하게 Conquer한 subproblems를 다시 병합할 필요가 없기 때문에 이 부분은 생략.

시간이 오래 걸리고 헛돌았던 이유는

1. for문에 들어가는 index를 정확하게 파악하고 지정해줬어야 하는데 착각하여 index를 해결해줘야 하는 부분에서 시간을 잡아먹음. 코드를 짜면서 "왜 이렇게 코드를 짜는지" 생각하는 습관을 들이자.
2. Divide가 된 사각형에 대해서는 다시 조사할 필요가 없는데 종료를 하지 않아 해당 사각형을 또 Divide 하고 Divide 해서 값이 중복적으로 증가했다.
3. 문제를 정확히 인지하지 않고 코드 작성에 들어가 목적에 부합하지 않는 결과를 출력했다.

---

과거에 이 문제를 풀었는데 현재 정석적으로 푼 것보다 시간이 훨씬 빨라 파이썬스럽게 효율적으로 코드를 작성하는 부분에 대해 공부할 경 비교하여 정리한다.

1. 값을 key로 만든 dictionary를 활용한 깔끔한 코드.
   

2. 시간 단축, 효율성을 위한 조건, 분기 위치 중요
   

3. 함수에 매개변수 전달.
   dq(N,(y,x)) -> dq에서 dq(n,s)로 받아 y=s[0],x=s[1]로 처리하는 것보다 dq(N,y,x) -> dq에서 dq(n,y,x) 바로 하면 속도가 유의미하다고 느낄 정도로 속도가 향상된다.