난이도

Silver 1

풀이 참고 유무

?

막힌 부분

시간초과

문제

문제 바로가기

입력

첫째 줄에 정수 N, r, c가 주어진다.

출력

r행 c열을 몇 번째로 방문했는지 출력한다.

예제 입력

10 512 512

예제 출력

786432

문제 검토

재귀 문제로 보인다.
4개로 쪼개서 문제를 풀이한다.

풀이

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.nio.Buffer;
import java.util.*;
import java.lang.*;
//아이디어
//최소 크기는 2x2
//matrix를 나누는 것 중요함
//divide(srow,scol,n//2)
//divide(srow,scol+n//2,n//2)
//divide(srow+n//2,scol,n//2)
//divide(srow+n//2,scol+n//2,n//2)
//위 형태로 쪼개면 될 듯
//n이 1이면 리턴
//방문할 때 마다 카운트를 하고 특정 행렬에 도달하면 그 숫자를 출력하고 리턴
//시간복잡도
//2의 14의 제곱이 이 행렬의 최대 크기가 되기 때문에
//n이 1이 될 때까지 재귀를 해버리면 주어진 시간인 0.5초는 너무 짧아서 시간초과가 난다.
//따라서 1~4사분면에 속하는지 확인 후 그 해당 사분면에서만 재귀를 돌린다.
public class z {
    static int[][] matrix;
    static int cnt;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int N,r,c;
        st=new StringTokenizer(br.readLine()," ");
        N=Integer.valueOf(st.nextToken());
        r=Integer.valueOf(st.nextToken());
        c=Integer.valueOf(st.nextToken());
        int n=(int)Math.pow(2,N);
        divide(r,c,n,r,c);
        System.out.println(cnt);
     }
    public static void divide(int trow,int tcol,int n,int row,int col) {
        if(n == 1){
            return;
        }
        if(row < n/2 && col < n/2) {
            divide(trow,tcol,n/2, row, col);
        }
        else if(row < n/2 && col >= n/2) {
            cnt += n * n / 4;
            divide(trow,tcol,n/2, row, col - n/2);
        }
        else if(row >= n/2 && col < n/2) {
            cnt += (n * n / 4) * 2;
            divide(trow,tcol,n/2, row - n/2, col);
        }
        else {
            cnt += (n * n / 4) * 3;
            divide(trow,tcol,n/2, row - n/2, col - n/2);
        }
    }
}

조건문으로 어느 사분면에 해당하는지 확인하는 것이 중요함

아이디어:

주석참고

걸린 시간

총평

어떠한 숫자를 몇번째 탐색하는지 확인하는 문제였기에 처음부터 카운트를 할 생각으로 문제를 풀었으나 난이도를 보고 시간 제한을 확인하지 않아서 실수를 했다.
시간복잡도를 계산하고 문제를 들어가는 것이 중요하다.