백준 14500번 테트로미노

문제

나의 풀이

import java.util.*;

public class Main {
    static int a[][];
    static boolean c[][];
    static int n, m;
    static int dx[] = { 0, 0, 1, -1 };
    static int dy[] = { 1, -1, 0, 0 };
    static int answer = 0;
    static void go(int x, int y, int sum, int count) {
        if(count == 4) { // 도형 1개 완성
            answer = Math.max(answer, sum); // 최댓값 구하기
            return;
        }
        // 불가능한 경우
        if(x < 0 || x >= n || y < 0 || y >= m) { // 범위 밖
            return;
        }
        if(c[x][y]) { // 이미 방문한 경우
            return;
        }
        
        c[x][y] = true; // 방문함
        for(int k = 0; k < 4; k++) {
            go(x + dx[k], y + dy[k], sum + a[x][y], count + 1); // 다음 칸
        }
        c[x][y] = false; // 초기화
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        a = new int[n][m];
        c = new boolean[n][m];
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                a[i][j] = sc.nextInt();
            }
        }
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                go(i, j, 0, 0); // 재귀 함수 호출
                if(j + 2 < m) {
                    int temp = a[i][j] + a[i][j + 1] + a[i][j + 2];
                    if(i - 1 >= 0) { // ㅜ
                        int temp2 = temp + a[i - 1][j + 1];
                        answer = Math.max(answer, temp2);
                    }
                    if(i + 1 < n) { // ㅗ
                        int temp2 = temp + a[i + 1][j + 1];
                        answer = Math.max(answer, temp2);
                    }
                }
                if(i + 2 < n) {
                    int temp = a[i][j] + a[i + 1][j] + a[i + 2][j];
                    if(j + 1 < m) { // ㅏ
                        int temp2 = temp + a[i + 1][j + 1];
                        answer = Math.max(answer, temp2);
                    }
                    if(j - 1 >= 0) { // ㅓ
                        int temp2 = temp + a[i + 1][j - 1];
                        answer = Math.max(answer, temp2);
                    }
                }
            }
        }
        System.out.println(answer);
    }
}

하나를 제외한 나머지 테트로미노는 임의의 한 칸에서 시작해서 3개의 칸을 연속해서 방문한 형태이다. 하나의 재귀 함수로는 할 수 없기 때문에 for문으로 살펴본다.

결과

백준 16197번 두 동전

문제

나의 풀이

import java.util.*;

public class Main {
    static int n, m;
    static char a[][];
    static final int dx[] = { 0, 0, 1, -1 };
    static final int dy[] = { 1, -1, 0, 0 };
    static int go(int step, int x1, int y1, int x2, int y2) {
        if(step == 11) { // 불가능한 경우
            return -1;
        }
        boolean fall1 = false; // 동전1이 떨어졌는지 여부
        boolean fall2 = false; // 동전2가 떨어졌는지 여부
        if(x1 < 0 || x1 >= n || y1 < 0 || y1 >= m) { // 범위 밖인 경우
            fall1 = true; // 동전1 떨어짐
        }
        if(x2 < 0 || x2 >= n || y2 < 0 || y2 >= m) { // 범위 밖인 경우
            fall2 = true; // 동전2 떨어짐
        }
        
        if(fall1 && fall2) { // 두 동전 모두 떨어진 경우
            return -1;
        }
        if(fall1 || fall2) { // 한 동전만 떨어진 경우
            return step; // 최소값 리턴
        }
        
        int answer = -1;
        for(int k = 0; k < 4; k++) { // 상하좌우 이동
            int nx1 = x1 + dx[k];
            int ny1 = y1 + dy[k];
            int nx2 = x2 + dx[k];
            int ny2 = y2 + dy[k];
            if(0 <= nx1 && nx1 < n && 0 <= ny1 && ny1 < m && a[nx1][ny1] == '#') { // 이동할 칸이 벽인 경우
                nx1 = x1; // 이동 안함
                ny1 = y1; 
            }
            if(0 <= nx2 && nx2 < n && 0 <= ny2 && ny2 < m && a[nx2][ny2] == '#') {
                nx2 = x2; // 이동 안함
                ny2 = y2;
            }
            
            int temp = go(step + 1, nx1, ny1, nx2, ny2);
            if(temp == -1) { // 불가능한 경우
                continue;
            }
            if(answer == -1 || answer > temp) {
                answer = temp; // 최소값 구하기
            }
        }
        return answer;
    }
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        a = new char[n][m];
        int x1, y1, x2, y2;
        x1 = y1 = x2 = y2 = -1;
        for(int i = 0; i < n; i++) {
            a[i] = sc.next().toCharArray();
            for(int j = 0; j < m; j++) {
                if(a[i][j] == 'o') {
                    if(x1 == -1) {
                        x1 = i;
                        y1 = j;
                    } else {
                        x2 = i;
                        y2 = j;
                    }
                    a[i][j] = '.';
                }
            }
        }
        System.out.println(go(0, x1, y1, x2, y2));
    }
}

go 함수의 매개변수 step은 버튼을 누른 횟수, (x1, y1)은 한 동전의 위치, (x2, y2)는 다른 동전의 위치를 뜻한다.
불가능한 경우는 step이 11일 때나 두 동전 모두 떨어진 경우이다.
정답을 찾은 경우는 두 동전 중에서 하나만 떨어진 경우다.
다음 경우는 상하좌우를 누르는 경우다.

결과

백준 16198번 에너지 모으기

문제

나의 풀이

import java.util.*;

public class Main {
    static int go(ArrayList<Integer> a) {
        int n = a.size();
        if(n == 2) { // 불가능한 경우
            return 0;
        }
        int answer = 0;
        for(int i = 1; i < n - 1; i++) {
            int energy = a.get(i - 1) * a.get(i + 1); // 에너지 계산
            ArrayList<Integer> b = new ArrayList<>(a); 
            b.remove(i); // 현재 구슬 제거 
            energy += go(b); // 다음 경우
            answer = Math.max(answer, energy); // 최댓값 구하기
        } 
        return answer;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        ArrayList<Integer> a = new ArrayList<>();
        for(int i = 0; i < n; i++) {
            a.add(sc.nextInt());
        }
        System.out.println(go(a));
    }
}

go 함수는 에너지 구슬의 무게가 w에 순서대로 저장되어있을 때 모을 수 있는 에너지의 최댓값을 뜻한다.

결과

인프런 겹쳐진 압축 해제

문제

나의 풀이

import java.util.*;

public class Decompress {
    public static String solution(String s) {
        String answer = "";
        Stack<String> stack = new Stack<>();
        for(Character x : s.toCharArray()) {
            if(x == ')') {
                String tmp = "";
                while(!stack.isEmpty()) {
                    String c = stack.pop();
                    if(c.equals("(")) {
                        String num = "";
                        while(!stack.isEmpty() && Character.isDigit(stack.peek().charAt(0))) {
                            num = stack.pop() + num;
                        }
                        String res = "";
                        int count = 0;
                        if(num.equals("")) {
                            count = 1;
                        } else {
                            count = Integer.parseInt(num);
                        }
                        for(int i = 0; i < count; i++) {
                            res += tmp;
                        }
                        stack.push(res);
                        break;
                    }
                    tmp = c + tmp;
                }
            } else {
                stack.push(String.valueOf(x));
            }
        }
        for(String x : stack) {
            answer += x;
        }
        return answer;
    }
    public static void main(String[] args) {
        System.out.println(Decompress.solution("3(a2(b))ef"));
        System.out.println(Decompress.solution("2(ab3((cd)))"));
        System.out.println(Decompress.solution("2(2(ab)3(2(ac)))"));
    }
}

결과