[SCPC] 2024 SCPC 예선 1차 1번, 2번

대문자 A와 B로 구성된 문자열이 주어진다. 철수는 문자열의 연속인 부분에 A가 B보다 더 많은 것을 싫어한다. 부분의 길이가 1인 경우에도 A가 더 많지 않아야 한다면 문자열에 A가 하나도 없어야 한다. 그래서 철수는 길이가 1인 경우는 고려하지 않기로 하였다. 즉, 철수는 문자열에서 연속이고 길이가 2 이상인 어떤 부분에서도 A의 개수가 B의 개수보다 많지 않기를 원한다. 철수가 할 수 있는 일은 주어진 문자열에 B를 끼워 넣는 것이다. 철수가 목적을 달성하기 위해 끼워 넣어야 하는 B의 최소 개수를 계산하는 프로그램을 작성하라.

문자열이 “ABAA”인 경우를 생각해 보자. 연속이고 길이가 2 이상인 부분들 중 A가 더 많은 경우는 “ABA”, “BAA”, “ABAA”, "AA"의 4가지가 있다. B를 3개 추가하여 문자열을 “ABBABBA”로 바꾸면 연속이고 길이가 2 이상인 모든 부분에서 A가 더 많지 않음을 알 수 있다. B를 2개 이하로 추가하는 방법들을 다 따져 보면 모두 조건을 만족시킬 수 없음을 알 수 있다. 

 

입력 파일에는 여러 테스트 케이스가 포함될 수 있다.
파일의 첫째 줄에 테스트 케이스의 개수를 나타내는 정수 T𝑇 가 주어지고,
이후 차례로  T𝑇 개의 테스트 케이스가 주어진다. ( 1≤T≤501≤𝑇≤50 ) 
각 테스트 케이스의 첫 줄에는 문자열의 길이를 나타내는 정수 N𝑁이 주어진다 ( 4≤N≤300,0004≤𝑁≤300,000 ).
다음 줄에는 입력 문자열이 주어진다. 입력 문자열은 대문자 A와 B로만 구성된다.

- 점수 : 각 제출에서 취득한 점수 중에서 최대 점수 (만점 100점)
  주어지는 테스트 케이스 데이터들의 그룹은 아래와 같으며,
 각 그룹의 테스트 케이스를 모두 맞추었을 때 해당되는 부분 점수를 받을 수 있다.

ㆍ 그룹 1 (27점) : 4≤N≤84≤𝑁≤8
ㆍ 그룹 2 (12점) : 4≤N≤504≤𝑁≤50
ㆍ 그룹 3 (61점) : 추가적인 제약조건이 없다.

 

입력

3
4
ABAA
4
BBBA
5
ABABA

출력

Case #1
3
Case #2
0
Case #3
2

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

public class Main {

    static int Answer;
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);

        int T = sc.nextInt();
        for(int test_case = 0; test_case < T; test_case++) {
            Answer=0;
            int temp =0;//a 위치
            boolean first=false;
            int n= sc.nextInt();//갯수
            String s= sc.next();
            String[] strarr= s.split("");//배열로저장
            if(strarr.length==1){
                if (strarr[0].equals("A")) {
                    Answer=1;
                }else{
                    Answer=0;
                }
            }else if(strarr.length==2){
                if(strarr[0].equals("A")){
                    if(strarr[1].equals("A")){
                        Answer=2;
                    }else{
                        Answer=0;
                    }
                }else{
                    Answer=0;
                }
            }else{
                for(int i = 0; i < n; i++) {
                    if(strarr[i].equals("A")) {
                        if(!first){//처음 a일때
                            temp=i;
                            first=true;
                        }else{
                            if(i-temp>=3){//a와 a사이에 b가2개 이상
                                Answer+=0;
                            }else{
                                Answer+=2-(i-temp-1);
                            }
                            temp=i;
                        }
                    }
                }
            }
            System.out.println("Case #"+(test_case+1));
            System.out.println(Answer);
        }
    }
}

2번

철수는 N개의 물건을 배달해야 한다. N은 4의 배수이다. 철수는 각 물건의 무게를 알고 있다. 한번 나갈 때마다 철수는 4개의 물건을 한꺼번에 가져간다. 4개의 물건들의 무게가 각각 a,b,c,d라고 하자. 반드시 a≤b≤c≤d𝑎≤𝑏≤𝑐≤𝑑가 되도록 물건의 무게를 정렬해야 한다. 이때, 철수가 버는 금액은 |d−c|+|c−b|+|b−a|+|a−d||𝑑−𝑐|+|𝑐−𝑏|+|𝑏−𝑎|+|𝑎−𝑑|이다. N/4번의 배달에서 철수가 버는 총 금액이 가장 크도록 물건들을 잘 골라서 배달할 수 있게 도와주는 프로그램을 작성하라.

물건이 4개가 있고, 무게들이 각각 1,2,3,4라고 하자. 이 경우 철수는 단 한번, 모든 물건을 들고 나가게 된다. 이 때 버는 금액은 |4-3|+|3-2|+|2-1|+|1-4|=6이다. 이번에는 물건이 8개가 있고 무게들이 각각 1,2,3,4,5,6,7,8이라고 하자. 철수는 2번 나가게 된다. 첫번째에 가져가는 물건들의 무게가 각각 1,4,5,7이라고 하면 이때 버는 금액은 |7-5|+|5-4|+|4-1|+|1-7|=12이다. 두번째에 철수가 가져가는 물건들의 무게는 각각 2,3,6,8이 되고, 버는 금액은 |8-6|+|6-3|+|3-2|+|2-8|=12이다. 총 금액은 24가 되며, 이 금액이 가능한 가장 큰 금액이다.

 

입력 파일에는 여러 테스트 케이스가 포함될 수 있다.
파일의 첫째 줄에 테스트 케이스의 개수를 나타내는 정수 T𝑇 가 주어지고,
이후 차례로  T𝑇 개의 테스트 케이스가 주어진다. (1≤T≤501≤𝑇≤50) 
각 테스트 케이스의 첫 줄에는 물건의 개수를 나타내는 정수 N𝑁이 주어진다 (4≤N≤300,0004≤𝑁≤300,000).
N𝑁은 4의 배수임이 보장된다.
다음 줄에 물건들의 무게들이 1 이상 1,500,000 이하의 정수로 주어진다.

- 점수 : 각 제출에서 취득한 점수 중에서 최대 점수 (만점 150점)
  주어지는 테스트 케이스 데이터들의 그룹은 아래와 같으며,
 각 그룹의 테스트 케이스를 모두 맞추었을 때 해당되는 부분 점수를 받을 수 있다.


ㆍ 그룹 1 (38점) : 4≤N≤84≤𝑁≤8
ㆍ 그룹 2 (31점) : 4≤N≤204≤𝑁≤20
ㆍ 그룹 3 (81점) : 추가적인 제약조건이 없다. 

3
4
1 2 3 4
4
1 1 1 1
8
1 2 3 4 5 6 7 8

Case #1
6
Case #2
0
Case #3
24

 

 

 

import java.io.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main {

    static long Answer;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        for(int test_case = 0; test_case < T; test_case++) {
            Answer=0;
            int N = Integer.parseInt(br.readLine());//물건의 갯수
            StringTokenizer st = new StringTokenizer(br.readLine());
            ArrayList<Integer> list = new ArrayList<>();

            // 모든 토큰을 ArrayList에 추가
            while (st.hasMoreTokens()) {
                list.add(Integer.parseInt(st.nextToken()));
            }
            Collections.sort(list);
            int sumNum=N/4;//앞에랑 뒤에서 몇개 더해서 함께 빼야 하는지, 그 결과를 몇번 곱해야 하는지
            for (int i = 0; i < sumNum; i++) {
                Answer+=(list.get(N-sumNum+i)-list.get(i))*2L;
            }
            System.out.println("Case #"+(test_case+1));
            System.out.println(Answer);
        }
    }
}