[문제풀이] 백준 1074 - Z

kodaaa·2022년 12월 1일
0

문제풀이

목록 보기
11/23
post-thumbnail

📢 문제

https://www.acmicpc.net/problem/1074

📢 알고리즘

분할과 정복, 재귀

📢 풀이

💡 분할과 정복 tip

  • 호출할 함수 정의
  • 함수(시작x, 시작y, 변의길이) 식으로 코드 짜려고 노력!
#include <iostream>
#include <math.h>

using namespace std;
int N = 0, r = 0, c = 0;
int result = 0;

//x,y : 칸 시작 좌표
//n : 칸 크기
void divide(int x, int y, int n)
{
    // n=1일 때
    if (x == r && y == c)
    {
        cout << result;
        exit(0);
    }
    //그 칸 안에 있는지 확인
    if (x <= r && r < x + n && y <= c && c < y + n)
    {
        //칸 안에 있으면 쪼개기
        divide(x, y, n / 2);
        divide(x, y + n / 2, n / 2);
        divide(x + n / 2, y, n / 2);
        divide(x + n / 2, y + n / 2, n / 2);
    }
    else
    {
        //칸 안에 없으면 칸 내 블록개수 만큼 더함
        result += n * n;
    }
}

int main()
{
    cin >> N >> r >> c;
    divide(0, 0, pow(2, N));
}
  • 입력인 r, c 좌표는 그대로 두되
    분할 함수의 시작 좌표(x,y)를 변의 크기(n)만큼 계속 더해서 업데이트!

참고
https://hevton.tistory.com/419

profile
취뽀하자(●'◡'●)💕

0개의 댓글