패스트캠퍼스 챌린지 35일차

모의 코딩 테스트 풀이 1

 

홀수 홀릭 호석 (BOJ 20164)

 

 - 완전 탐색 (재귀 함수가 제일 좋다)

 - 함수 디자인

   1. 매 순간 들고 있는 수 : x

   2. 시작부터 지금까지 얻은 점수, total_odd_cnt

 

재귀함수 조건

 1. 종료 조건 -> x가 한자리 수인 경우

 2. 아닌 경우 -> 가능한 경우로 모두 잘라서 다음 수에 대해 재귀 호출

 

별도 함수

 - 수에 포함된 홀수의 개수를 계산해주는 함수

 

구현

 

    static int N, ans_min, ans_max;
    static PrintWriter out = new PrintWriter(System.out);
    
    static void pro(){
        ans_min = 0x7fffffff;
        ans_max = 0;
        // 시작하는 순간에는 N 이라는 숫자와, 여기에 속한 홀수 개수 만큼이 포함된다.
        dfs(N, get_odd_cnt(N));
        System.out.println(ans_min + " " + ans_max);
    }

    public static void main(String[] args) {
        input();
        pro();
    }

    // x 라는 수 안에 홀수의 개수를 return하는 함수
    static int get_odd_cnt(int x){
        int res = 0;
        while (x > 0){
            int digit = x % 10;
            if (digit % 2 == 1) res++;
            x /= 10;
        }
        return res;
    }
    // x 라는 수에 도달했으며, 이때까지 등장한 홀수 자릿수가 total_odd_cnt 만큼 있을 때, 남은 경우를 모두 잘라보는 함수
    static void dfs(int x, int total_odd_cnt) {

        // 만약 한 자리 수면 더 이상 작업을 반복할 수 없으므로 정답을 갱신하고 종료한다.
        if (x <= 9) {
            ans_min = min(ans_min, total_odd_cnt);
            ans_max = max(ans_max, total_odd_cnt);
            return;
        }

        // 만약 두 자리 수면 2개로 나눠서 재귀 호출한다.
        if (x <= 99) {
            int next_x = (x / 10) + (x % 10);
            dfs(next_x, get_odd_cnt(next_x) + total_odd_cnt);
            return;
        }

        // 만약 세 자리 이상의 수면 가능한 3가지 자르는 방법을 모두 진행한다.
        String s = Integer.toString(x);
        for (int i = 0; i <= s.length() - 3; i++) {
            for (int j = i + 1; j <= s.length() - 2; j++) {
                String x1 = s.substring(0, i + 1);  // s[0...i]
                String x2 = s.substring(i + 1, j + 1);  // s[i+1...j]
                String x3 = s.substring(j + 1, s.length());  // s[j+1...end]

                // 나눠진 세 수를 더해서 재귀 호출
                int next_x = Integer.parseInt(x1) + Integer.parseInt(x2) + Integer.parseInt(x3);
                dfs(next_x, get_odd_cnt(next_x) + total_odd_cnt);
            }
        }
    }

 

 

인내의 도미노

 - 시뮬레이션 문제

 

 

구현

  	static int n, m, R, ans;
    static int[][] a, backup;
    
    
    // 게임 순서에 맞게 진행시키는 함수
    static void pro() {
        for (int i = 1; i <= R; i++) {
            int X, Y;
            String dir;

            // 공격수 차례
            X = scan.nextInt();
            Y = scan.nextInt();
            dir = scan.next();
            attack(X, Y, dir.charAt(0));

            // 수비수 차례
            X = scan.nextInt();
            Y = scan.nextInt();
            a[X][Y] = backup[X][Y];
        }

        // 정답 출력
        System.out.println(ans);
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (a[i][j] == 0) System.out.print("F ");
                else System.out.print("S ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        input();
        pro();
    }

    // x 행 y 열에 있는 도미노를 dir 방향으로 밀어버리는 함수
    static void attack(int x, int y, char dir) {
        if (a[x][y] == 0) return;

        // dx, dy 는 도미노가 넘어지는 방향을 좌표 변화량으로 표현한 것
        int dx = 0, dy = 0;
        if (dir == 'E') dy = 1;
        else if (dir == 'W') dy = -1;
        else if (dir == 'S') dx = 1;
        else if (dir == 'N') dx = -1;

        // cnt := 앞으로 더 넘어져야 하는 거리를 나타내는 변수
        int cnt = a[x][y];
        while (x >= 1 && x <= n && y >= 1 && y <= m && cnt >= 1) {
            if (a[x][y] != 0) ans++;

            // 이번에 넘어진 a[x][y] 에 의해서, 넘어져야 하는 거리가 더 길어지는 경우를 확인!
            cnt = max(cnt - 1, a[x][y] - 1);

            // 넘어뜨리기
            a[x][y] = 0;

            // 다음 방향 확인하기
            x += dx;
            y += dy;
        }
    }

 

 

 

 

 

 

 

35일차 인증

 

 

 

 

본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.

https://bit.ly/37BpXiC

패스트캠퍼스 [직장인 실무교육]