https://www.acmicpc.net/problem/1074
백준 1074번 문제이다.
실버 1정도 되는 난이도이다.
문제에서 재귀적으로 순서대로 방문한다는 조건이 있어,
재귀로 풀어야겠다는 생각을 해보았다
문제
풀이
Divide and conquer(분할 정복) 알고리즘을 활용했는데,정사각형의 중심을 기준으로
왼쪽위(1사분면)
오른쪽위(2사분면)
왼쪽아래(3사분면)
오른쪽 아래(4사분면) 총 4개로 나누었다.
각자 4개로 나누어진 부분에서도 방금 했던 방법처럼 4개로 나눌 수 있고, 이게 계속 반복되어 제일 작은 단위가 될때까지(n=1이 될때까지) 재귀적으로 반복하여 값을 return 받을 수 있도록 하였다
main 메서드에서 Scanner를 통해 값을 입력받은후, 이를 recur 메서드에서 재귀로 반복하도록 메서드를 구현하였다.
Base case를 n==0일때, 즉 네모의 크기가 0일때 0을 리턴하도록 하였고, size라는 변수가 항상 정사각형의 중심을 나타내도록 하였다. (한 변의 크기가 8까지이면 인덱스는 0~7이기 때문에 Math.pow(2, n-1) 를 하면 된다)
이제 1-4분면을 if/ else if 문으로 조건을 나누어(앞에서 만든 size 변수를 활용) count 변수에 값을 더해주는데, 1사분면은 추가적으로 더해주는 값이 없고, 2사분면은 하나의 사분면의 크기만큼, 3사분면은 두 사분면의 크기만큼, 4사분면은 3개의 사분면의 크기만큼 더해주고, 이 값에 재귀적으로 한 사분면의 값을 추출해서 더해준다.
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int r = sc.nextInt();
int c = sc.nextInt();
int count = recur(n, r, c);
System.out.print(count);
}
private static int recur(int n, int r, int c) {
if (n == 0) {
return 0;
}
int size = (int) Math.pow(2, n - 1);
int count = 0;
if (r < size && c < size) { // 제 1사분면
count += recur(n - 1, r, c);
} else if (r < size && c >= size) { // 제 2사분면
count += size * size;
count += recur(n - 1, r, c - size);
} else if (r >= size && c < size) { // 제 3사분면
count += 2 * size * size;
count += recur(n - 1, r - size, c);
} else { // 제 4사분면
count += 3 * size * size;
count += recur(n - 1, r - size, c - size);
}
return count;
}
}
후기
알고리즘 강의를 들은지 어느덧 7개월,,,,
오랜만에 재귀적으로 짜야하는 코드를 만들어보았다
오랜만에 해보아서 머리도 좀 아프고 잘 안되었는데,
기본적인 문제라 다음에 다시 한번 풀어볼만한 문제인거 같다
