[python 백준] 2630번 색종이 만들기

문제 링크

문제 설명

• 얼룩 덜룩한 색종이를 절반씩 잘라가며 한가지 색으로만 이뤄진 정사각형 모양의 색종이가 나올 때 까지 계속해서 자른 후 흰색과 파란색 색종이의 수를 각각 구하는 것

고민한 부분

• 반복문을 중첩해 풀이하려고 시도를 했으나 전체 종이의 크기에 따라 반복 횟수가 달라지기 때문에 반복문으로 풀이하는 것이 어렵다고 판단했다.
• 지금까지 공부한 내용 안에서 정해지지 않은 횟수의 중첩 반복문제를 해결하는 방법은 $^{1)}$재귀와 $^{2)}$그래프 탐색 알고리즘(BFS, DFS)가 있다.
  • 문제를 분석해 보았을 때 DFS나 BFS로 탐색할 수 있는 그래프 형태로 만들 수 있는 방법을 떠올리지 못했다.
  • 반복되는 부분을 찾아 재귀 함수로 문제를 구현하기로 생각했다.
• 나는 재귀 함수를 구현할 때는 종료 조건 코드를 먼저 작성하고 작업 내용을 나중에 작성하는 편이다.
  • 종료 조건 : 도화지 크기가 1 or 도화지가 모두 같은 색으로 이뤄져있을 때
  • 종료시 작업 : 색종이의 색에 따라 흰색, 파란색 도화지 수를 증가시킨다.
  • 반복 작억 : 도화지를 4등분해 각각에 대해 함수를 반복한다.

재귀 함수 반복 내용

• 재귀 함수의 argument를 결정하기 위해 그림을 그려 해결 과정을 한번 그려보았다.
• 시작 좌표가 (R,C)이고 도화지 한 변의 길이가 L일 때, 종료 조건을 확인하고 종료 조건을 만족시키지 못했을 때 4 등분 후 각각에 대해 조건 확인을 반복한다.
  • 이 과정에서 재귀 함수에 필요한 argument는 시작점의 좌표(R,C)와 색종이의 크기 L로 결정하면 되는 것을 확인했다.

Lesson learned

• 문제 풀이에 막혔을 때, 막힌 원인을 파악하고 그 원인을 해결하기 위해 내가 가지고 있는 도구가 무엇인지 나열해 생각해보는 것이 필요하다는 것을 생각했다. 수능 수학 문제를 풀 때 이런 식으로 사고를 했었는데 여전히 유효한 사고 방법인 것 같다.