[코드트리 조별과제] 2024/07/30 - 트로미노, 금 채굴하기, 기울어진 직사각형

오늘의 계획

• 코드트리 문제풀이 - 구현
• 정보처리기사 실기 정리
• 토익스피킹 공부

---

코드트리 문제풀이

트로미노

내 풀이

• 모양이 제한되어 있기에, 모든 노드를 기준으로 범위 내 인지 체크하고 각 모양 별 값을 구해서 최댓값을 구하면 된다고 생각했다.
• 반복문으로 구해도 되지만 많지 않은 크기이기에 반복문을 사용하는 것보다 하드 코딩하는 것이 시간이 짧게 걸릴 것같아서 하드 코딩으로 짜기로 했다.

import java.util.*;

public class Main {
    static int n, m;
    static int ans = 0;
    static int[][] matrix;

    public static void main(String[] args) {
        init();

        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                check1(i, j);
                check2(i, j);
            }
        }

        System.out.println(ans);
    }

    private static void init() {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        matrix = new int[n][m];

        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                matrix[i][j] = sc.nextInt();
            }
        }
    }

    private static void check1(int row, int col) {
        // ㄴ 모양
        if(inScope(row - 1, col) && inScope(row, col + 1)) {
            ans = Math.max(ans, matrix[row][col] + matrix[row - 1][col] + matrix[row][col + 1]);
        }

        // 90도 돌린 모양
        if(inScope(row + 1, col) && inScope(row, col + 1)) {
            ans = Math.max(ans, matrix[row][col] + matrix[row + 1][col] + matrix[row][col + 1]);
        }

        // 180도 돌린 모양
        if(inScope(row + 1, col) && inScope(row, col - 1)) {
            ans = Math.max(ans, matrix[row][col] + matrix[row + 1][col] + matrix[row][col - 1]);
        }

        // 270도 돌린 모양
        if(inScope(row - 1, col) && inScope(row, col - 1)) {
            ans = Math.max(ans, matrix[row][col] + matrix[row - 1][col] + matrix[row][col - 1]);
        }

    }

    private static void check2(int row, int col) {
        // 가로
        if(inScope(row, col + 2)) {
            ans = Math.max(ans, matrix[row][col] + matrix[row][col + 1] + matrix[row][col + 2]);
        }

        // 세로
        if(inScope(row + 2, col)) {
            ans = Math.max(ans, matrix[row][col] + matrix[row + 1][col] + matrix[row + 2][col]);
        }
    }

    private static boolean inScope(int row, int col) {
        if (0 <= row && row < n && 0 <= col && col < m) 
            return true;
        else
            return false;
    }
}

 

---

금 채굴하기

내 풀이

• 델타탐색을 활용해서 풀면 되겠다는 생각이 들었다.
• 마름모의 경우, 각 좌표의 절댓값의 합이 K보다 작거나 같은 범위라는 것을 찾았고, 이중 반복문을 통해 모든 좌표에서 가능한 마름모의 갯수를 구하면 된다고 생각했다.

import java.util.*;

public class Main {
    static int n, m;
    static int ans = 0;
    static int maxProfit = 0;
    static int[][] matrix;

    public static void main(String[] args) {
        init();

        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                solve(i, j);
            }
        }

        System.out.print(ans);
    }

    private static void init() {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        m = sc.nextInt();

        matrix = new int[n][n];

        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                matrix[i][j] = sc.nextInt();
            }
        }
    }

    private static boolean inScope(int row, int col) {
        if (0 <= row && row < n && 0 <= col && col < n)
            return true;
        return false;
    }

    private static int findOutCost(int ground) {
        return ground * ground + (ground + 1) * (ground + 1);
    }

    private static void solve(int row, int col) {
        for(int k = 0; k <= n; k++) {
            int gold = 0;

            for(int i = -k; i <= k; i++) {
                for(int j = -k; j <= k; j++) {
                    if (Math.abs(i) + Math.abs(j) > k) continue;
                    int nx = row + i;
                    int ny = col + j;

                    if (inScope(nx, ny)) {
                        if (matrix[nx][ny] == 1) gold++;
                    }
                }
            }

            if(gold * m - findOutCost(k) >= 0) {
                ans = Math.max(ans, gold);
            }
        }
        

    }
}

---

기울어진 직사각형

내 풀이

• 이중 반복문으로 inRange 즉, 영역을 벗어나는 경우 방향을 바꿔주는 방식으로 값을 구하면 되며,
  음수가 없기에, 무조건 항 방향으로 끝까지 가는 경우를 계산하는 것이 최대값이라고 생각했다.
  (단, 네 모서리에 접근하는 경우 직사각형이 안되기 때문에 예외처리가 필요하다.)
  끝까지 이동하지 않고 방향을 바꾸는 경우, 최대값이 될 수 있다.
  즉, 각 노드 별 이동가능한 모든 경우의 수를 확인해야 최대값을 구할 수 있다.
• 각 노드 별로 직진 or 방향 전환 두 가지 경우만 있기 때문에 재귀로 풀었다.
• 예외처리를 잘 해줘야 한다.

import java.util.*;

public class Main {
    static int n;
    static int ans = 0;
    static int[][] matrix;
    static int startRow, startCol;
    static int[] dx = {-1, -1, 1, 1};
    static int[] dy = {1, -1, -1, 1};

    public static void main(String[] args) {
        init();

        for(int i = 2; i < n; i++) {
            for(int j = 1; j < n - 1; j++) {
                startRow = i;
                startCol = j;
                solve(i, j, 0, 0);
            }
        }

        System.out.println(ans);
    }

    public static void init() {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        matrix = new int[n][n];

        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                matrix[i][j] = sc.nextInt();
            }
        }
    }

    public static void solve(int row, int col, int dir, int value) {
        if(row == startRow && col == startCol && dir == 3) {
            ans = Math.max(ans, value);
            return;
        }

        if(dir == 3 && (row > startRow || col > startCol)) return;

        int nx = row + dx[dir];
        int ny = col + dy[dir];

        if(inRange(nx, ny)) {
            solve(nx, ny, dir, value + matrix[nx][ny]);
        }

        if(dir == 3 || row == startRow && col == startCol) return;

        nx = row + dx[dir + 1];
        ny = col + dy[dir + 1];

        if(inRange(nx, ny)) {
            solve(nx, ny, dir + 1, value + matrix[nx][ny]);
        }
    }

    public static boolean inRange(int row, int col) {
        if(0 <= row && row < n && 0 <= col && col < n) {
            if((row == 0 || row == n || row == -n) && (col == 0 || col == n || col == -n)) return false;
            return true;
        }
        return false;
    }
}

---

오늘의 회고

• 오늘 계획한 일을 못했다.
  내가 생각하는 원인으로 "비합리적인 시간 분배"였다고 생각한다.
  > 알고리즘 한 문제에 너무 많은 시간을 할애했다. 적정 시간을 정해놓고 풀어야겠다.