문제를 어떻게 접근해야할까?
ㄴ아래 사진을 보면 너무너무 복잡하다. 게다가 시간 제한이 0.5초이다. 그냥 브루트포스로는 불가능 할 것다.
ㄴ그렇다면 분할정복으로 접근해볼까?
일단 아이디어를 생각해보자. 저 grid를 1사분면 2사분면 3사분면 4사분면으로 계속 나누어서 하면 되지 않을까?
아래 그림으로 예를 들어 설명하면 우측 상단에 있는 21을 찾는다면. 저렇게 1/4로 반갈죽 계속 시켜서 쌓아가는 느낌이면 될 것같다.
분할정복 문제이므로 3가지를 먼저 생각해보자.
1. 언제 재귀하지 않아도 되는가?
ㄴ문제가 n>1인 경우에 계속 호출한다니까 n=0이면 얼추 되겠다.
2. 어떻게 n을 나눠야 할까?
ㄴ흠.. 고민이 된다.
3. 어떻게 합쳐야할까?
ㄴ그냥 계속 더하면 될 것 같다.
#include <iostream>
#include <vector>
#include<cmath>
using namespace std;
int solve(int n, int r, int c) {
int grid = pow(2, n) / 2;
if (n == 0)
return 0;
//위
if (grid > r) {
if (grid > c)
return solve(n-1, r, c); // 왼
else
return grid*grid + solve(n-1,r,c-grid); //오
}
//아래
else {
if (grid > c)
return 2* grid*grid + solve(n-1,r-grid,c); // 왼
else
return 3*grid*grid + solve(n-1, r-grid, c-grid); //오
}
}
int main() {
int n, r, c; // 3행 1열
cin >> n >> r >> c;
cout << solve(n, r, c) << '\n';
}
요즘 기분이 정말 좋지 않다. 가을을 타나 보다. 어디론가 떠나고 싶다는 생각도 많이 든다. 그냥 지금까지 모은 돈으로 세계일주라도 다녀올까? 워킹홀리데이라도 다녀올까 싶기도 하다. 뭔가 인생노잼 시기 같다. 지금 올바르게 살고 있는가 싶기도 하고 왠지 모르게 우울하기도 하고 그냥 눈물이 나오기도 한다. 고민이 많다. 뭐 그래도 이또한 지나가겠지
김동율의 jump라는 노래를 들으면 뭔가 내 상황 같아서 위로가 되는 것 같다. 유튜브 제이레빗이 부른게 난 뭔가 더 심금을 울리는 것 같다. 다들 한번 들어보길 바란다. 뭐 글의 두서가 없긴 하지만 다들 힘든 일이 있다면 힘내길 바란다. 지금 하는 일이 잘 되지 않아도 인생의 짧은 순간일 뿐이다. 뭐 힘들때는 올라잇 정신으로 지내보자