[BEAKJOON] 1074_Z_C언어

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

풀이

어렵지 않은 문제 같은데..맞추는데 시간이 오래걸린 문제이다.

처음에 문제에서 말하는대로 배열 채워가면서 정답을 출력하려고 하였으나...시간도 초과날 뿐만아니라 배열이 너무커서 선언도 안 되었다.

그래서 생각을 해보니 규칙이 있었다!!!!

위 사진에서 보는 것 처럼 왼쪽 위를 x라고 하며, 오른쪽 위 - 왼쪽 위 = y라고 하겠다. 그럼

왼쪽 위 : x

오른쪽 위 : x + y

왼쪽 아래 : x + 2*y

오른쪽 아래 : x + 3*y

의 규칙이 있다. y는 N에 따라 계산가능하다.

N은 1일때 1, 2일때 4, 3일때 16 ....과 같이 증가한다.

문제에서 예제로 주어진 3 7 7을 예로 들어보겠다.

재귀 함수에서 전달되는 인자값은 3개이다. 답이 있는 구간의 빨간점의 위치에 있는 수들의 합, y,그리고 배열의 길이이다.

3 7 7 에서 초기 수들의 합 num 0, y는 16, 배열의 높이 len 8로 메인문에서 재귀함수를 호출한다.

Z(0,16,8)

4개의 구간에서 7,7은 왼쪽 아래에 있으므로 다음 재귀에 왼쪽 위의 빨간 점의 값 num+y*3,y/4,len/2을 넘겨준다. 그리고 중요한게 배열의 크기가 작아졌으므로 R C의 값도 이에 비례해서 작아져야된다.

R=R-len/2; C=C-len/2;

z(48,4,4)

이 배열은 위의 초록색으로 동그라미된 부분만을 나타낸 것이다. 여기서 R=3;C=3;위치에 우리가 원하는 답이 있다. 따라서 검은색 동그라미가 우리가 원하는 답이 있는 구간이다. 인자로 넘어온 값이 y가 4이므로 빨간점에서의 값은 num+3*y=60이 된다. 여기서 num은 왼쪽 위 사각형의 초기값이 된다. 위에서 했던 것 처럼 num+y*3,y/4,len/2을 인자로 넘겨주면된다.

z(48+4*3,1,2)

마지막 사각형도 똑같이 해주면 된다. 더 쪼갤게 없으면 return해준다.

제출코드

#include <stdio.h>
int N,n=2,answer,a,b,w=1,x,y;
 
void z(int num, int k,int len)
{    
    answer = num;
    if (len / 2 > b&&len / 2 > a)//왼쪽 위
    {
        z(num, k / 4, len / 2);
    }
    else if (len / 2 <= a&&a < len&&len / 2 <= b&&b < len)//오른쪽 아래
    {
        a = a - len / 2; b = b - len / 2;
        z(num + k * 3, k / 4, len / 2);
    }
    else if (len / 2 > a&&len / 2 <= b&&b < len)//오른쪽 위
    {    
        b = b - len / 2;
        z(num + k, k / 4, len / 2);
    }
    else if (len / 2 <= a&&a < len&&b < len / 2)//왼쪽 아래
    {
        a = a - len / 2;
        z(num + k * 2, k / 4, len / 2);
    }
    return;
}
 
int main()
{
    scanf("%d %d %d",&N,&a,&b);
    y = a; x = b;
    for (int i = 1; i < N; i++)
        n = n*2;
 
    for (int i = 1; i < N; i++)
        w = w * 4;
 
    z(0,w,n);
 
    printf("%d\n",answer);
 
    return 0;
}

#백준 #C언어 #알고리즘 #1074z