[BOJ 12969] ABC (Java)

BOJ 12969 ABC

난이도 : 골드 1

https://www.acmicpc.net/problem/12969

12969번: ABC

 

전략

 'A'의 개수 a, 'B'의 개수 b로 이루어진 길이가 len인 문자열에서 조건을 만족하는 쌍이 pair만큼 있다면

len + 1 길이의 문자열에서의 pair은 다음과 같다.

1. 'A' 선택 : pair

2. 'B' 선택 : pair + a

3. 'C' 선택 : pair + a + b

 

이전 길이의 문자열에서의 'A', 'B', 'C'의 위치와 관계 없이 개수 a, b에 따라 다음 길이 문자열의 pair이 결정되므로

중복되는 연산을 제거할 수 있다.

 

시행착오

dp에서 항상 특정 상태에서 최적의 값을 저장하다가,

문제의 특이한 구조로 어떻게 저장해야할지 고민이 많이 되었다.

 

처음에는 dp[len][a][b]의 3차원 배열에 int형으로 pair를 저장하려고 했지만

반환 처리를 어떻게 할지 고민하다가 이렇게 구성하였다.

 

코드

import java.util.Scanner;

public class Main {

    static int N, K;
    static char[] seq;
    static boolean[][][][] dp;

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

        seq = new char[N + 1];
        dp = new boolean[N + 1][N + 1][N + 1][N * (N - 1) / 2 + 1];

        if (solution(0, 0, 0, 0))
            System.out.println(seq);
        else
            System.out.println(-1);
    }

    static boolean solution(int len, int a, int b, int pairs) {
        if (len == N) {
            if (pairs == K)
                return true;
            return false;
        }

        if (dp[len][a][b][pairs])
            return false;
        dp[len][a][b][pairs] = true;

        seq[len] = 'A';
        if (solution(len + 1, a + 1, b, pairs)) return true;
        seq[len] = 'B';
        if (solution(len + 1, a, b + 1, pairs + a)) return true;
        seq[len] = 'C';
        if (solution(len + 1, a, b, pairs + a + b)) return true;

        return false;
    }

}

 

깨달은 점

메모이제이션으로 중복 연산을 줄이는 방법이 바로바로 떠오를 때까지 열심히 연습해야겠다.