IT Docs

문제 링크 : https://www.acmicpc.net/problem/5904

Moo 게임 문제를 접했을 때 메모리 제한을 간과하고 moomooomoo... 이런 식으로 문자열을 만들었다.
하지만 메모리 초과가 발생하여 다시 풀었지만 접근조차 하지 못했다.
문제 자체는 이해하기 쉽지만 구현해 내기에는 센스가 필요하다고 생각됐다.
결국 그 센스를 발휘하지 못하여 상당히 분했지만 이런 유형의 문제를 익힌다는 마음으로 학습하고 머릿속에 각인시켰다.

아래와 같이 소스를 공유 합니다.

import java.util.Scanner;

public class Main {
    public static String ans;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        
        moo(n);
        
        System.out.println(ans);
    }
    
    public static void moo(int num) {
        int side = 3;
        int center = 0;
        
        while(num > side) {
        	// 4를 더하는 이유는 두번째 수열을 더하기 위함
            side = center + 4 + side * 2;
            center++;
        }
        
        // 3을 빼주는 이유는 while문에서 center는 1씩 증가해서
        // center+4가 실제 가운데 영역보다 1크기 때문에 
        int fb = (side - center - 3) / 2;
        
        if(side - fb+1 <= num) {
            moo(num - side+fb);
        }else if(num == fb+1) {
            ans = "m";
        }else {
            ans = "o";
        }
    }
}

문제 링크 : https://www.acmicpc.net/problem/1780

종이의 개수 문제를 접했을 때 분할 하는 방법을 몰랐다.

그래서 아래의 색종이 만들기 문제를 먼저 풀면서 분할 정복의 핵심 로직을 익혔다.

두 문제를 다 풀어보니 둘중 뭐가 더 어렵다고 말하기 힘들정도로 비슷하다.

종이의 개수 문제가 분할의 범위가 커졌을뿐이다.

그래도 분할의 범위가 작은 색종이 만들기 부터 풀고나니 종이의 개수 문제를 대하는 태도가 달라졌다.

난이도 낮은 문제를 푼게 아주 큰 도움이 되었다.

nkt-docs.tistory.com/21

다음과 같이 소스를 공유합니다.

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

public class 종이의 개수 {
    public static int N;
    public static int[][] map;
    public static int[] res = new int[3];
    public static void main(String[] arsg) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        N = Integer.parseInt(br.readLine());
        
        map = new int[N][N];
        
        for(int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            for(int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        divide(0, 0, N);
        
        StringBuilder sb = new StringBuilder();
        
        sb.append(res[2]).append("\n");
        sb.append(res[0]).append("\n");
        sb.append(res[1]).append("\n");
        
        System.out.println(sb.toString());
    }
    
    public static void divide(int r, int c, int s) {
        if(checkNum(r, c, s)) {
            int num = map[r][c];
            if(num == -1) {
                res[2]++;
            }else {
                res[num]++;
            }
            return;
        }
        
        int ns = s/3;
        
        divide(r, c, ns);
        
        divide(r, c+ns, ns);
        divide(r, c+ns*2, ns);
        
        divide(r+ns, c, ns);
        divide(r+ns*2, c, ns);
        
        divide(r+ns, c+ns, ns);
        
        divide(r+ns, c+ns*2, ns);
        divide(r+ns*2, c+ns, ns);        
        
        divide(r+ns*2, c+ns*2, ns);
    }
    
    public static boolean checkNum(int r, int c, int s) {
        int num = map[r][c];
        
        for(int i = r; i < r+s; i++) {
            for(int j = c; j < c+s; j++) {
                if(map[i][j] != num) return false;
            }
        }
        
        return true;
    }
}

핵심 로직은 divide를 재귀로 호출하는 부분이다.

divide의 파라미터를 r(row), c(col), s(size)로 받는다.

r = 0, c = 0, s = 9

예를 들면

1. 배열[0][0] ~ 배열[8][8] 까지 배열을 체크(checkNum)하여 같은 종이인지 확인(if문) 후 해당 번호의 종이를 +1한다.

2. s(size)를 3으로 나누어 분할 한다.

3. 배열[0][0] ~ 배열[2][2] 까지 배열을 체크(checkNum)하여 같은 종이인지 확인(if문) 후 해당 번호의 종이를 +1한다.

4. 배열[0][2] ~ 배열[2][4] 까지 배열을 체크(checkNum)하여 같은 종이인지 확인(if문) 후 해당 번호의 종이를 +1한다.

5. 배열[0][4] ~ 배열[2][6] 까지 배열을 체크(checkNum)하여 같은 종이인지 확인(if문) 후 해당 번호의 종이를 +1한다.

이런식으로 전체 배열의 시작 위치와 탐색해야 하는 크기를 이용하여 1칸의 종이까지 체크할 수 있다.

문제 링크 : www.acmicpc.net/problem/2630

스터디에서 분할 정복 문제인 백준 1780(종이의 개수)를 처음 접했다.
처음 접했을 때 문제의 흐름이나 코드 구성을 어떤 방식으로 구현해야 할지 단박에 이해됐다.
하지만 핵심 로직인 2차원 배열의 위치(1~4사분면)을 분할하는 로직을 생각해내지 못했다.
핵심 로직을 도움 없이 머릿속으로 구상하려고 하니 시간이 지날수록 머릿속은 복잡해졌다.
조금 더 여려 운 문제인 종이의 개수(Silver II)보다는 쉬운 색종이 만들기(Silver III)를 먼저 풀면서 핵심 로직을 익히기로 하였다.
등급이 조금 더 낮다고 해서 핵심 로직이 떠오르지는 않아 내가 모르는 것을 인정하고(상당히 분하지만..) 다른 분들의 코드를 보고 분석하면서 문제를 풀었다.

다음과 같이 소스를 공유합니다.

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

public class 색종이 만들기 {
    public static int N;
    public static int[][] map;
    public static int[] res = new int[2];    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        for(int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            for(int j = 0; j < N; j++) {
               map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        divide(0, 0, N);
        
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < res.length; i++) {
            sb.append(res[i]).append("\n");
        }
        
        System.out.println(sb.toString());
    }
    
    public static void divide(int r, int c, int s) {
        if(checkColor(r, c, s)) {
            if(map[r][c] == 0) {
                res[0]++;
            }else {
                res[1]++;
            }
            return;
        }
        
        int ns = s/2;
        
        divide(r, c, ns);
        divide(r, c+ns, ns);
        divide(r+ns, c, ns);
        divide(r+ns, c+ns, ns);
    }
    
    public static boolean checkColor(int r, int c, int s) {
        
        int color = map[r][c];
        
        for(int i = r; i < r+s; i++) {
            for(int j = c; j < c+s; j++) {
                if(map[i][j] != color) {
                    return false;
                }
            }
        }
        
        return true;
    }
}

핵심 로직은 divide를 재귀로 호출하는 부분이다.

divide의 파라미터를 r(row), c(col), s(size)로 받는다.

r = 0, c = 0, s = 8

예를 들면

1. 배열[0][0] ~ 배열[7][7] 까지 배열을 체크(checkColor)하여 같은 종이인지 확인(if문) 후 해당 번호의 종이를 +1한다.

2. s(size)를 2으로 나누어 분할 한다.

3. 배열[0][0] ~ 배열[3][3] 까지 배열을 체크(checkColor)하여 같은 종이인지 확인(if문) 후 해당 번호의 종이를 +1한다.

4. 배열[0][4] ~ 배열[3][7] 까지 배열을 체크(checkColor)하여 같은 종이인지 확인(if문) 후 해당 번호의 종이를 +1한다.

이런식으로 전체 배열의 시작 위치와 탐색해야 하는 크기를 이용하여 1칸의 종이까지 체크할 수 있다.