kevinla   1년 전

처음엔 2n * 2n 에 해당 규칙을 적용시켜 채워 넣은 다음 [r][c]을 찾는 문제인가 고민했었습니다. 근데 그러면 테이블을 채워 나가는 규칙도 어렵거니와 규칙을 만든다고 해도 시간 초과가 나올 가능성이 크기에 저 방법은 안되고 다른 방법을 찾기 시작했습니다. 

예시는 (타자로 치는 사정상...) n = 3부터 봅시다.

0   1  4   5  16  17 20 21

2   3   6  7  18  19 22 23

8   9  12 13 24 25 28 29

10 11 14 15 26 27 30 31

32 33 36 37 48 49 52 53

34 35 38 39 50 51 54 55

40 41 44 45 56 57 60 61

42 43 46 47 58 59 62 63

우리가 고민해야 되는건 배치되는 규칙을 알아내 r행 c열에 숫자가 몇이 박힐지 계산하면 됩니다. 말은 간단하죠? 차근차근 알아가면 되겠습니다.

다음을 생각해보세요

1. n이 증가하거나 감소하면 테이블이 어떻게 바뀌지?

2. 어떤 숫자가 박힐지 확실하게 아는 방법은 무엇이지?

3. r,c는 어떻게 스케일링 해야지?

1번 고민은 생각할것도 없이 그냥 n이 증가할 수록 같은 규칙으로 똑같은 넓이 3개짜리 사각형이 붙어서 n + 1의 넓이인 정사각형이 됩니다.

그럼 거꾸로 생각해서 n - 1로 하나씩 내려가면 왼쪽위의 사각형만 따오면 되겠군요 = n번째 정사각형을 4등분해 사분면으로 만들면 2사분면이 n - 1번 테이블이겠군요

그럼 테이블이 어떻게 바뀌는지 알았으니 숫자가 어떻게 박힐지 한번 고민해볼까요? 그럼 사분면으로 나누었으니 사분면으로 나눴을때 왼쪽 위에 있는 숫자를 볼까요?

각사분면의 가장 왼쪽 위의 숫자를 사분면의 숫자라 부르겠습니다.(너무 길어용..)

위의 n = 3은 순서대로 0(2사분면),16(1사분면),32(3사분면),48(4사분면)이군요. 16에 0,1,2,3을 곱했네요?

그럼 n = 2는요? 0,4,8,12... 4에 0,1,2,3을 곱했네요?

마지막 n = 1은 0,1,2,3... 1에 0,1,2,3을 곱했네요?

더 정확히 찾고 싶으면 n = 4일때까지 보는게 확실하겠지만 귀찮은 관계로 이정도로 규칙을 추론해봅시다. 

n = 1 => 1 = 20 , n = 2 => 4 = 22 , n = 3 => 16 = 24, ....

그럼 n = k일때는 사사분면의 가장 왼쪽위는 22(k - 1) 에 적절한 숫자(0,1,2,3)를 곱하면 구할 수 있겠군요

그럼 일반적인 경우는 어떨까요? 위의 테이블에서 1사분면을 쪼개서 새로운 사분면을 만들었다고 생각합시다. 그럼 각 사분면의 숫자는?

16,20, 24, 28이네요? 모두 16 + (4 * k) 꼴이군요. 그럼 저 16은 n = 3일때 1사분면의 숫자였죠? 그럼 (n = 3의 1사분면 숫자) + (4 * k) 가 되는군요!

n = k 일때 r 과 c가 몇사분면에 포함되어있는지 확인후 각 사분면의 숫자를 구한뒤 n을 줄여나가면서 더해가면 되겠네요
무조건 첫 시작은 0으로 시작하니, 순서대로 구하면서 더해가면? 끝!...인줄 알았으나 문제가 생겼네요... r, c를 어떻게 스케일링하죠?

사분면으로 쪼개면서 추적해 나가니 r,c의 절대적인 위치는 무용지물이니 상대적인 위치를 구해야겠군요 근데 이건 생각보다 간단하죠?

n = 3일때는 테이블을그려 볼까요?

               r < 4 = 22 = 2(n - 1)                       r >= 4

c < 4       2 사분면                               3 사분면

c >=4      1 사분면                               4 사분면

스케일링은 간단합니다. 2(n - 1)이상이면 2(n - 1)를 빼주면 새로운 사분면의 위치에서도 같은 위치인 r,c를 찾을 수 있죠?

자, 필요한 논리 설명은 다 했습니다.

마지막으로 이 논리로 풀 수 있는지 3 7 1로 풀어볼까요?

1) n = 3

1사분면의 숫자는 0, 단위는 16이고 (r,c) = (7,1)이니까 3사분면이군요 그럼 n = 2일때의 1사분면 숫자는 0 + 16 *2 = 32입니다. 그럼 rc를 스케일링하면  (7 => 3, 1)이 됩니다.

2) n = 2
1사분면의 숫자는 32, 단위는 4이고 (r,c) = (3,1)이니까 3사분면이군요 그럼 n = 1 일때의 1사분면 숫자는 32 + 4 *2 = 40입니다. 그럼 rc를 스케일링하면 (3 => 1, 1)이 됩니다.

3) n = 1
1사분면의 숫자는 40, 단위는 1이고 (r,c) = (1,1)이니까 4사분면이군요 그럼 n = 0 일때의 1사분면 숫자는 40 + 1 * 3= 43입니다. 그럼 rc를 스케일링하면 (1 => 0, 1 => 0)이 됩니다.

4) n = 0

n이 0이면 끝난거지요? 그럼 아까 구했던 숫자인 43이 정답이 됩니다.

끝~~

이렇게하면 시행횟수도 제시된 n번 시행하면 되니 시간 초과 걱정도 없네요~ 재귀로 할지 반복문으로 구할지는 취향껏~
모두 고생하세요~~💪🏻💪🏻💪🏻💪🏻💪🏻

h_charn   1년 전

와우

2014amy   7달 전

와우...

댓글을 작성하려면 로그인해야 합니다.