12969번 - ABC(bfs, dp)

문제:

 

풀이:

문자열 ABC의 유효한 쌍은 'AB', 'AC', 'BC'이다.

• A만 입력시에는 유효한 쌍이 없고,
• AB까지 입력시에는 유효한 쌍이 AB
• ABC까지 입력시에는 유효한 쌍에 AC, BC가 추가된다.

위 예시를 통해 알 수 있는 것은 아래와 같다.

• A 입력시 고려할 것은 없다
• B 입력시 앞에 있는 A의 수만 고려하면 된다.
• C 입력시 앞에 있는 A, B의 수를 고려해야 한다.
• C를 문자열의 앞 부분에 추가할 때 고려해야 할 것은 없다.

즉, A의 수, B의 수, C의 수, 유효한 쌍의 수 4개를 기록해 놓으면, 다음 문자를 추가할 때 계산을 편하게 할 수 있다.

계산 과정은 아래와 같다.

1. 기록한 정보를 꺼내온다.
2. 유효한 쌍의 수가 K와 같다면, "C * (N - (A + B + C의 수) ) + 만들어진 문자"를 출력한다.
3. 기록한 정보에서 A의 수, B의 수, C의 수의 합이 N보다 크거나 같다면 건너 뛴다.
4. 기록된 A의 수 + 1, 기록된 B의 수, 기록된 C의 수, 기록된 유효한 쌍, 기록된 문자 + "A"를 저장한다.
5. 만약 기록된 A의 수 + 기록된 유효한 쌍의 수가 K 보다 작거나 같다면
   1. 기록된 A의 수, 기록된 B의 수 + 1, 기록된 C의 수, 기록된 유효한 쌍 + A의 수, 기록된 문자 + "B"를 저장한다.
6. 만약 기록된 A, B의 수 + 기록된 유효한 쌍의 수가 K 보다 작거나 같다면
   1. 기록된 A의 수, 기록된 B의 수, 기록된 C의 수 + 1, 기록된 유효한 쌍 + A,B의 수, 기록된 문자 + "C"를 저장한다.
7. 1 ~ 6번 과정을 2번 조건이 만족하거나 기록된 정보가 없을 때 까지 반복한다.
8. 기록된 정보가 없다면 -1을 출력한다.

위 과정을 보면, BFS가 생각날 것이다, 어떤 정보를 기록하고 꺼내 쓰려면 queue 자료구조형이 적합할 것이다.

 

또한 A의 수, B의 수, C의 수, 유효한 쌍이 같다면 a,b,c 순서에 상관없이, 다음에 나올 유효한 쌍의 결과가 같다.

이렇게 중복을 피하기 위해 DP를 함께 사용한다면, 문제를 풀 수 있을 것이다.

 

위의 설명대로 코드를 작성하면 아래와 같다.

static String dpBfs(int N, int K) {
    String[][][][] dp = new String[N+1][N+1][N+1][K+1]; // dp[a][b][c][쌍]

    Queue<int[]> queue = new LinkedList<>();
    queue.add(new int[]{0,0,0,0});

    while (!queue.isEmpty()) {
        int[] cur = queue.poll();
        int a = cur[0];
        int b = cur[1];
        int c = cur[2];
        int sum = cur[3];
        String now = dp[a][b][c][sum];
        if (now == null) { // null 지워야함 안그러면 nullABC 처럼 이상하게 나옴
            now = "";
        }

        if (sum == K) { // 목표값까지 도달 시
            int temp = N - a - b - c;
            if (temp > 0) { // 문자를 다 쓰지 않아도 앞에 C로 채워넣으면 됨
                now = "C".repeat(temp) + now;
            }
            return now;
        }

        if (a + b + c >= N) { // 문자를 다 썼다면 건너 뛰기
            continue;
        }

        // 사용된 abc 수와 그에 따른 순서쌍의 수가 같다면, abc의 순서에 상관 없이 중복임
        if (dp[a+1][b][c][sum] == null) {
            dp[a+1][b][c][sum] = now + "A";
            queue.add(new int[]{a+1,b,c,sum});
        }
        if (sum + a <= K && dp[a][b+1][c][sum+a] == null) {
            dp[a][b+1][c][sum+a] = now + "B";
            queue.add(new int[]{a,b+1,c,sum+a});
        }
        if (sum + a + b <= K && dp[a][b][c+1][sum + a + b] == null) {
            dp[a][b][c+1][sum+a+b] = now + "C";
            queue.add(new int[]{a,b,c+1,sum+a+b});
        }
    }
    return "-1";
}

 String 배열은 초기화시 null이 저장되고, 그 상태에서 + "A"와 같은 연산을 수행하면 nullA로 저장된다.

고로 null 일때는 배열에 ""를 대신 저장해준다.

목표값에 도달했지만 주어진 문자를 다 사용하지 않았을 때는 위에서 설명한 바와 같이 문자열 앞부분에 C를 추가해준다.

ABC와 CCCABC는 사용한 문자 수는 다르지만, 유효한 쌍의 수가 같다.

 

전체코드: 

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();

        System.out.println(dpBfs(N, K));
    }

    static String dpBfs(int N, int K) {
        String[][][][] dp = new String[N+1][N+1][N+1][K+1]; // dp[a][b][c][쌍]

        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{0,0,0,0});

        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int a = cur[0];
            int b = cur[1];
            int c = cur[2];
            int sum = cur[3];
            String now = dp[a][b][c][sum];
            if (now == null) { // null 지워야함 안그러면 nullABC 처럼 이상하게 나옴
                now = "";
            }

            if (sum == K) { // 목표값까지 도달 시
                int temp = N - a - b - c;
                if (temp > 0) { // 문자를 다 쓰지 않아도 앞에 C로 채워넣으면 됨
                    now = "C".repeat(temp) + now;
                }
                return now;
            }

            if (a + b + c >= N) { // 문자를 다 썼다면 건너 뛰기
                continue;
            }

            // 사용된 abc 수와 그에 따른 순서쌍의 수가 같다면, abc의 순서에 상관 없이 중복임
            if (dp[a+1][b][c][sum] == null) {
                dp[a+1][b][c][sum] = now + "A";
                queue.add(new int[]{a+1,b,c,sum});
            }
            if (sum + a <= K && dp[a][b+1][c][sum+a] == null) {
                dp[a][b+1][c][sum+a] = now + "B";
                queue.add(new int[]{a,b+1,c,sum+a});
            }
            if (sum + a + b <= K && dp[a][b][c+1][sum + a + b] == null) {
                dp[a][b][c+1][sum+a+b] = now + "C";
                queue.add(new int[]{a,b,c+1,sum+a+b});
            }
        }
        return "-1";
    }
}

 

시행착오:

String 배열이 초기화되면 null이 저장되어 있다는 것은 알았지만,

그 상태에서 문자열 "ABC"가 추가되면, nullABC가 되는것은 몰랐다.

이유는 참조타입, null 문자열 연산에 있다.

1. String 배열은 참조타입이기 때문에 모든 요소는 기본적으로 null로 초기화 된다.
2. Java에서는 문자열 결합 연산이 수행될 때, 피연산자가 문자열이 아닌 경우 String.valueOf() 라는 메서드가 호출된다.
   이 메서드는 피연산자가 null일 경우 "null"문자열을 반환한다.

 

DP에 대한 여러 문제를 풀어보았다. 중간까지는 감을 잘 잡지 못했지만,

마지막 문제까지 풀다보니, 점점 시간과 오답률이 줄어들었다.
앞으로 어려운 DP 문제가 나와도 잘 해결할 수 있을 것 같다.