저번에 못풀었던 문제를 다시 풀었어요.
분할 정복 형식으로 풀고, 재귀 함수를 이용하였습니다!!
문제
한수는 2차원 배열 (항상 2^N * 2^N 크기이다)을 Z모양으로 탐색하려고 한다. 예를 들어, 2*2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다.
만약, 2차원 배열의 크기가 2^N * 2^N라서 왼쪽 위에 있는 칸이 하나가 아니라면, 배열을 4등분 한 후에 (크기가 같은 2^(N-1)로) 재귀적으로 순서대로 방문한다.
다음 예는 2^2 * 2^2 크기의 배열을 방문한 순서이다.
N이 주어졌을 때, (r, c)를 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오.
다음 그림은 N=3일 때의 예이다.
입력
첫째 줄에 N r c가 주어진다. N은 15보다 작거나 같은 자연수이고, r과 c는 0보다 크거나 같고, 2^N-1보다 작거나 같은 정수이다
출력
첫째 줄에 문제의 정답을 출력한다.
예제 입력
2 3 1
예제 출력
11
출처: https://www.acmicpc.net/problem/1074
아래의 소스를 참고하세욧!!
오랜만에 비트 shift도 썼네... 헷... 뿌듯합니다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | #include <stdio.h> int n, r, c; int go(int length, int x, int y) { //length:행(열)의 개수, x: current row, y: current cloumn //재귀를 멈추기 위한 제약식 if (length == 1) return 0; //bound: 사분면의 경계 int bound = length >> 1; //사분면 최소값을 더해주기 위한 변수 int min = bound * bound; if(x < bound && y < bound) return go (bound, x, y); else if (x < bound && y >= bound) return min + go(bound, x, y - bound); else if (x >= bound && y < bound) return min * 2 + go(bound, x - bound, y); return min * 3 + go(bound, x - bound, y - bound); } int main() { scanf("%d%d%d", &n,&r,&c); printf("%d", go(1 << n, r, c)); } | cs |
'알고이즘 > 문제를 막풀어' 카테고리의 다른 글
| [boj]1004 어린왕자 (0) | 2017.12.04 |
|---|---|
| [boj] no.1003 피보나치 (0) | 2017.12.01 |
| [boj] no.2775 부녀회장이 될테야 (0) | 2017.11.29 |
| [boj] no.1074 z (2) | 2017.11.28 |
| [boj] no.1002 터렛 (1) | 2017.11.27 |