[BOJ, SWEA] #1074 Z, #2805 나무자르기, #정사각형방 (java)

#1074 Z

---

문제설명

1. N이 주어진다. 여기서 N은 2^N * 2^N으로 주어진다.

2. 행과 열이 주어질 때, 몇번째로 그 행과 열을 방문한지 출력해야 한다.

 

 

 

 

해결방법고안

1. 예시를 보면 분할 정복 문제임을 알 수 있다. 1사분면, 2사분면, 3사분면, 4사분면으로 계속해서 나눌 수 있다.

2. 따라서 재귀로 몇사분면인지 찾고, 몇번째로 방문했는지 계속해서 더하면 된다.

 

그래서 find함수를 작성해서 사분면으로 나누고 몇번째인지 count를 더해주었다.

private static void find(int r, int c, int size){
    if(size == 1) {
        return;
    }
    if(r < size/2 && c < size/2) { // 1사분면
        find(r,c,size/2);
    }
    else if(r< size/2 && c >= size/2){ //2사분면
        find(r, c-size/2, size/2);
        count += size*size/4;
    }
    else if(r >= size/2 && c<size/2 ) { //3사분면
        find(r-size/2, c,size/2);
        count += (size*size/4)*2;
    }
    else if(r>=size/2 && c>=size/2) { //4사분면
        find(r-size/2, c-size/2, size/2);
        count += (size*size/4)*3;
    }
}

 

종료 조건은 더 이상 나눌 수 없을 때, size가 1일 때이다.

파라미터로 들어오는 r, c에 따라 사분면이 나누어진다. 

반으로 나누었을 때 기준으로 범위에 따라 1,2,3,4를 조건 별로 나누어 작성하였다.

count 같은 경우도 size*size/4를 하는 이유가 사분면으로 나누고 그 중에서 몇번째 방문인지 더하주기 위함이다.

 

전체코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJZ {
    private static StringTokenizer tokens;
    private static StringBuilder output = new StringBuilder();
    private static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    private static int n,row,col,count;
    public static void main(String[] args) throws IOException {
        tokens = new StringTokenizer(input.readLine());
        n = Integer.parseInt(tokens.nextToken());
        row = Integer.parseInt(tokens.nextToken());
        col = Integer.parseInt(tokens.nextToken());
        int size = (int) Math.pow(2, n);
        find(row, col, size);
        System.out.println(count);
    }
    private static void find(int r, int c, int size){
        if(size == 1) {
            return;
        }
        if(r < size/2 && c < size/2) { // 1사분면
            find(r,c,size/2);
        }
        else if(r< size/2 && c >= size/2){ //2사분면
            find(r, c-size/2, size/2);
            count += size*size/4;
        }
        else if(r >= size/2 && c<size/2 ) { //3사분면
            find(r-size/2, c,size/2);
            count += (size*size/4)*2;
        }
        else if(r>=size/2 && c>=size/2) { //4사분면
            find(r-size/2, c-size/2, size/2);
            count += (size*size/4)*3;
        }
    }
}

 

 

#2805 나무자르기

---

문제설명

1. n개의 나무가 있을 때 높이를 설정해서 적어도 m개만큼 가져가야한다.

2. 적어도 m개를 가져가면서 최대 높이 나무를 설정해야 한다.

 

해결방법고안

n의 범위와 m의 범위가 보다 싶이 엄청 크다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000)

완탐으로 풀 수 있는 문제이지만 이렇게 범위가 클 때는 이진탐색을 이용하자

이진탐색은 반씩 높이를 조정하기 때문에 시간 초과가 나지 않을 가능성이 높다.

 

나는 이 문제를 파이썬으로 풀었었는데, 자바로 다시 풀어봤는데 주의해야 할 점이 있었다.

int를 long으로 써야한다는 것,,!

보다 싶이 범위가 커서 내가 사용한 sum은 int의 범위를 넘어간다. 그래서 계속 답이 틀렸었다.

 

그리고 적어도 m만큼이니까 sum이 m을 넘어가면 일단 답으로 저장을 해놓고, 높이의 최대값을 찾기 위해서 start = mid+1를 해준다.

 

전체코드

package boj;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Boj2805 {
    private static StringTokenizer tokens;
    private static StringBuilder output = new StringBuilder();
    private static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    private static int n,m;
    private static int tree[];
    public static void main(String[] args) throws IOException {
        tokens = new StringTokenizer(input.readLine());
        n = Integer.parseInt(tokens.nextToken());
        m = Integer.parseInt(tokens.nextToken());
        tree = new int [n];
        tokens = new StringTokenizer(input.readLine());
        for(int i=0; i<n; i++) {
            tree[i] = Integer.parseInt(tokens.nextToken());
        }
        Arrays.sort(tree);

        int res = 0;
        int start  = 0;
        int end = tree[n-1];

        while(start <= end) {
            int mid = ( start + end ) / 2;
            long sum =0;
            for(int i=0; i<n; i++) {
                if(tree[i] > mid) {
                    sum += (long)(tree[i] - mid);
                }
            }
            if(sum >= m) {
                res = mid;
                start = mid+1;
            }
            else{
                end = mid-1;
            }
        }
        System.out.print(res);
    }
}

 

 

#정사각형방

---

문제이해

1. n*n 정사각형방이 있다.

2. 정사각형 방 한 점에서 상하좌우로 이동할 수 있다.

3. 현재 점에서 이동하려는 점이 1만큼 차이가 나야 이동할 수 있다.

4. 총 이동 횟수의 최대값을 구해야한다. 그 시작점도 구해야 한다.

5. 최대값이 같은 좌표가 있으면 그 좌표값이 작은 점을 구해야 한다.

 

해결방법고안

1. 시작점을 다르게 1부터 n까지 설정한다.

2. bfs 함수를 만들어서 1부터 n까지의 최대값을 찾는다.

3. 1만큼 차이가 나도록 bfs함수 조건을 추가한다.

4. 최대값이 같을 때만 비교 조건을 넣었다.

 

전체코드

package swea;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

public class SWEA정사각형방 {
    private static StringTokenizer tokens;
    private static StringBuilder output = new StringBuilder();
    private static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));

    static int n;
    static int[][] map;
    static boolean[][] visited;
    static int [][] deltas ={{0,1}, {1,0}, {-1,0}, {0,-1}};

    public static void main(String[] args) throws IOException {
        int T = Integer.parseInt(input.readLine());
        for (int t = 1; t <= T; t++) {
            int max_val = Integer.MIN_VALUE;
            n = Integer.parseInt(input.readLine());
            map = new int[n][n];
            int room = Integer.MAX_VALUE;
            for(int i=0; i<n; i++) {
                tokens = new StringTokenizer(input.readLine());
                for(int j=0; j<n; j++) {
                    map[i][j] = Integer.parseInt(tokens.nextToken());
                }
            }

            for(int i=0; i<n; i++) {
                for(int j=0; j<n; j++) {
                    visited = new boolean[n][n];
                    int c = bfs(i,j,1); //완전탐색
                    if(c > max_val) {
                        max_val = c;
                        room = map[i][j];
                    } else if (c==max_val) {
                        if(room > map[i][j]) room = map[i][j];
                    }
                }
            }
            output.append("#").append(t).append(" ").append(room).append(" ").append(max_val).append("\n");
        }
        System.out.print(output);
    }

    static int bfs(int x, int y, int c) {
        Queue<int []> que = new ArrayDeque<>();
        que.offer(new int [] {x,y,c});
        visited[x][y] = true;
        while(!que.isEmpty()) {
            int t[] = que.poll();
            int dx = t[0];
            int dy = t[1];
            c = t[2];
            for(int d[]: deltas) {
                int nx = dx + d[0];
                int ny = dy + d[1];
                if(nx >=0 && nx<n && ny>=0 && ny<n && !visited[nx][ny]) {
                    if(Math.abs(map[dx][dy]-map[nx][ny]) ==1) {
                        que.offer(new int [] {nx,ny,c+1});
                        visited[nx][ny]= true;
                    }
                }
            }
        }
        return c;
    }
}