| def f(n, r, c) : if [n, r, c] == [0, 0, 0] : return 0 x = pow(2, n-1) if r < x and c < x : return f(n-1, r, c) elif r < x and c >= x : return f(n, r, c-x) + pow(x, 2) elif r>= x and c < x : return f(n, r-x, c) + 2 * pow(x, 2) elif r>= x and c>= x : return f(n, r-x, c-x) + 3 * pow(x, 2) n, r, c = map(int, input().split()) print(int(f(n, r ,c))) |
2차원 배열을 가로반 세로반 4등분 했을때, 좌상단 덩어리는 N=n-1의 배열과 같다. f(n, r, c) = f(n-1, r, c)
우상단 덩어리는 좌상단 덩어리에 4^(n-1)을 더한 것이고 f(n, r, c) = f(n, r, c-x) + 4^(n-1)
좌하단 덩어리는 좌상단 덩어리에 2* 4^(n-1)를 더한 것이고, f(n, r, c) = f(n, r-x, c) + 2* 4^(n-1)
우하단 덩어리는 3* 4^(n-1)을 더한 것이다. f(n, r, c) = f(n, r-x, c-x) + 3* 4^(n-1)
재귀함수를 정의하면 그냥 함수를 실행하고 print하면 된다.
글을 적으면서 보니 print를 굳이 int로 할 필요는 없었던 것 같다.
'Week 01 ~ 04 : 알고리즘 문제 풀이' 카테고리의 다른 글
| 파이썬 백준 10971 외판원 순회 2 (0) | 2021.11.09 |
|---|---|
| 파이썬 백준 10819 차이를 최대로 (0) | 2021.11.09 |
| 파이썬 백준 9663 N-Queen (0) | 2021.11.09 |
| 파이썬 백준 1914 하노이 탑 (0) | 2021.11.09 |
| 파이썬 백준 9020 골드바흐의 추측 (0) | 2021.11.09 |