[BOJ][Python]5956번 풀이

또 한동안 바빠서 못왔었는데요. 이제는 큰 불은 꺼서 다시 정기적으로 포스팅을 할 수 있을 것 같습니다.

 

최근에 백트래킹 공부를 계속 했었는데요. 제가 재귀 프로그래밍을 잘 못하다 보니 아이디어는 떠올라도 구현을 못하는 일이 비일비재하길래 재귀 구현 연습을 해야겠다는 생각이 들었습니다. 오늘 문제도 그 중 하나가 되겠네요.

 

문제 링크 : https://www.acmicpc.net/problem/5956

5956번: Symmetry

코드 : 

import sys
ssr = sys.stdin.readline

def cow(n,m,cnt,ans):
    if n%2 == 1 and m%2 == 1:
        ans += cnt
        cnt *= 4
        cow(n//2,m//2,cnt,ans)
    else:
        print(ans)
        return

n,m = map(int, ssr().split())# n = row, m = col
cow(n,m,1,0)

 

문제를 간단하게 해석을 해보자면, 대칭으로 계속 공간을 나누기 위해서 정중앙에 소를 배치하는데 더 이상 나눠지지 않을 때까지 소를 배치하면 소는 몇 마리가 필요할까? 라는 문제입니다. 소가 어쩌고 하니까 문제가 눈에 확 들어오지 않으실 수도 있겠네요. 즉, 가로, 세로를 반반 나눈 횟수는 몇 번이야?라는 문제라고 생각하시면 편할 것 같습니다.

 

최근 블로그 기록을 좀 봤는데 정말 이것 저것 올리고 있더라고요. 스케줄러도 중간에 멈춰있고, 이미지 프로세싱도 멈춰있고... 그래서 이제 주간별 목표를 정해서 일을 하려고 합니다. 다음 주 까지는 백준 골드 티어를 찍는 것을 목표로 할 계획이기 때문에 한동안은 백준 풀이 포스팅만 올라올 것 같습니다.