알고리즘 풀이 - 백준 12970(AB, 그리디(Greedy))

 

관련글

 

그리디 알고리즘 관련 포스팅은 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

문제의 내용은 아래의 더보기를 클릭하여 참조

 

N, K가 주어질 때, 아래 조건을 만족하는 문자열 S를 구하는 문제

 - 문자열 S의 길이가 N이고 'A', 'B'로만 이루어져있다.
 - S에는 $0 <= i <= j < N$ 이면서 S[i] == 'A' && S[j] == 'B'를 만족하는 (i, j)쌍이 K개 있다.

 

 

2. 풀이

 

이 문제에서는 우선 아래의 성질을 도출할 수 있다.

① 문자열의 길이가 N이므로 A와 B의 총 개수는 N이 된다.
② AB의 쌍은 $\sum$(A 1개 x A의 뒤에 위치한 B의 개수) = K

그렇다면 ①에 의해서 A가 M개 였다면 B는 N-M개를 쓸 수 있을 것이다.

 

이 때, ②에 의해서 AB의 쌍이 최대로 나올 수 있는 경우는 A가 모두 앞에 위치하고, 그 뒤에 모든 B를 위치시키는 방식일 것이다.
그 경우에 AB의 쌍은 최대 AxB개 만들 수 있다.(예 : AABB면 최대 AB 쌍은 4개)

그런데, 이 때, A와 B가 혼합되어 위치될 수 있기 때문에 현재 AxB < K라면 해당 A, B의 수로는 K쌍의 AB를 만들 수 없다는 뜻이다.
즉, $AxB \leqslant  K$인 경우에만 A와 B를 이용한 K쌍을 만드는 경우의 결과를 만들어낼 수 있다!

 

우선 첫째로 위의 내용을 기반으로 하여 반복문을 구현해 A, B의 적절한 개수를 지정해주자.

 

그러면 현재 A의 개수가 M개, B의 개수가 N-M개로 정해졌을 것이다. 예를 들어 N=5일 때, K=3을 만들고자 한다면 A가 2개, B가 3개인 경우가 있다고 해보자.

(N = 5, K = 3, A = 2, B = 3)

그러면, 이 때, 우선 B가 3개이므로 BBB와 같이 쓸 수 있을 것이다.

 

이 상태에서 첫 위치부터 각 B의 중간에 AB가 K쌍(예시에서 3쌍)이 될 때까지 A를 위치시키면 문제를 해결할 수 있다. 위의 예시에서는 아래와 같이 된다.
▶ ABBB

 

마지막으로, N개의 A, B를 모두 사용하지 않은 상태이므로 마지막에 A를 그 수만큼 붙여주면 문제가 해결된다.
▶ ABBBA

 

코드로 구현하면 약간 복잡한데, 아래에 주석을 상세히 써 놓았으니 참고해주세요.

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

import java.io.*;
import java.util.*;

public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split(" ");
        
        int n = Integer.parseInt(s[0]);
        int k = Integer.parseInt(s[1]);
        
        StringBuilder sb = new StringBuilder();
        // A의 개수가 0개부터 n개 까지 있을 수 있는 경우를 체크한다.
        for(int i=n; i >= 0; i--){
            int A = i;
            int B = n - i;
            
            // A*B가 K보다 작다면 K개의 AB 쌍을 만들 수 없으므로 넘어간다.
            if(A * B < k) continue;
            
            // cnt는 전체 문자를 몇개 적었는지 확인하기 위해 사용하는 변수
            int cnt = 0;
            
            // K부터 시작하여 0이 되면 AB쌍을 K개 만들었음을 확인하기 위한 변수
            int temp = k;
            
            // 우선 가능한 B를 모두 위치시키고 처음 및 각 B의 중간 위치에
            // A를 몇 개씩 놓아야 전체 쌍이 형성될 수 있는지를 체크
            for(int j=B; j >= 0; j--){
            
                // A의 개수를 각 위치에 놓는다.
                for(int a=i; a >= 0; a--){
                
                    // 현재 위치한 B의 앞에 A를 놓는데
                    // A*B가 temp보다 작은 경우에는 A는 a개 만큼 위치하고 B를 하나만 우선 놓는다.
                    if(temp > a*j){
                        temp -= a*j;
                        for(int t=0; t < a; t++){
                            sb.append("A");
                            cnt++;
                        }
                        sb.append("B");
                        cnt++;
                        break;
                    // A*B가 temp와 같다면 A와 B 모두 가능한 만큼 다 놓아야 한다.
                    } else if(temp == a*j){
                        temp -= a*j;
                        for(int t=0; t < a; t++){
                            sb.append("A");
                            cnt++;
                        }
                        for(int t=0; t < j; t++){
                            sb.append("B");
                            cnt++;
                        }
                        break;
                    }
                }
                
                // temp==0이라면 AB의 K쌍이 모두 만들어진 것
                if(temp == 0) {
                
                    // 만약 N개의 전체 문자를 다 못채웠다면 "A"를 뒤에 계속 붙인다.
                    while(cnt++ < n){
                        sb.append("A");
                    }
                    System.out.println(sb);
                    return;
                }
            }
        }
        System.out.println(-1);
        br.close();
    }
}

 

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.