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칸의 종이까지 체크할 수 있다.

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

이 문제는 배열 돌리기 1을 먼저 푼 후 접근하였다.

nkt-docs.tistory.com/18

두 문제의 차이점은 기본 로직은 동일 하나 어떤 값을 돌릴 것인지의 차이가 있다.

문제의 핵심

1. 2차원 정수 배열의 크기는 홀수 X 홀수이기 때문에 항상 가운데 지점이 존재한다.

1. 2차원 정수 배열의 크기는 홀수 X 홀수이기 때문에 항상 가운데 지점이 존재한다.
2. 배열의 첫 번째 트랙부터 가운데 지점까지(N/2) 반목문을 실행한다.
3. 가운데 지점에서 몇 번째 트랙인지를 체크하여 배열의 어떤 값을 돌릴지 구현한다.
   1. N이 5일 때, 첫 번째 트랙(가장 외곽)은 N/2 - x(행)을 계산하여 돌릴 값을 선택한다.
4. 각도의 값이 0보다 작으면 +8을 하여 항상 오른쪽 방향으로만 돌아가도록 구현한다.
   1. -45도일 경우, -45/45 == -1이므로 +8을 하여 7번 만큼 오른쪽으로 돌렸을 때 왼쪽으로 1번(-1) 돌린 위치가 된다.
5. 항상 오른쪽으로 배열을 돌리지만 실제로는 왼쪽(0,0 기준 하, 좌, 상, 우)으로 돌면서 값을 이동  시킨다.

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

public class 배열돌리기 {
	public static int N;
	public static int[][] map;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int t = Integer.parseInt(br.readLine());
		
		for(int z = 0; z < t; z++) {
			String[] str = br.readLine().split(" ");
			
			N = Integer.parseInt(str[0]);
			int c = Integer.parseInt(str[1]);
			
			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());
				}
			}
			
			if(c%360 != 0 ) {
				move(c/45);
			}
			
			StringBuilder sb = new StringBuilder();
			
			for(int i = 0; i < N; i++) {
				for(int j = 0; j < N; j++) {
                	// 움직인 배열을 보기 좋게 출력
					// sb.append(map[i][j] <= 9 ? "0"+map[i][j]:map[i][j]).append(" ");
                    sb.append(map[i][j]).append(" ");
				}
				sb.append("\n");
			}
			
			bw.write(sb.toString());
		}
		
		bw.flush();
		bw.close();
	}
	
	public static void move(int c) {
		int[] dx = {1, 0, -1, 0};
		int[] dy = {0, 1, 0, -1};
        // 가운데 지점
		int p = N/2;
		
		if(c < 0) c += 8;
		
		for(int i = 0; i < c; i ++) {
			for(int j = 0; j < N/2; j++) {				
				int x = j;
				int y = j;		
				int idx = 0;
				int temp = map[x][y];
				
				while(idx < 4) {
					int mx = dx[idx]*(p-j);
					int my = dy[idx]*(p-j);
					int xx = x + mx, yy = y + my;
					
					if(xx < j || yy < j || xx > N-j-1 || yy > N-j-1) {
						idx++;
					}else {
						map[x][y] = map[xx][yy];
						x = xx;
						y = yy;
					}
				}
                // 마지막 위치에 첫번째 값을 할당
				map[x][y+(p-j)] = temp;
			}
		}
	}
}