글 읽기 - 반례 좀 찾아주세요ㅠㅠ

06dyk26 3년 전 0

질문 게시판에 나온 반례 넣어봤는데ㅠㅠ 아직 왜 틀린 건지 모르겠어요ㅠㅠ

도움을 주신다면 정말 감사드립니다ㅠㅠ

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    static ArrayList arr; // 기본적인 'a ,c, i, n ,t'를 저장
    static ArrayList arr_add; // 위의 5가지 외에 문자열에 있는 추가적인 문자들
    static ArrayList arr_tmp; // arr_add에 있는 문자들 중 K-5개만큼 저장하면 임시 배열
    static String[] str_arr; // N개의 문자열 저장
    static int N, K, answer;

    public static void main(String[] args) throws Exception{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
        StringTokenizer st = new StringTokenizer(str);
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        answer = 0;
        if(K < 5) // K가 5 미만이면 0 출력 후 종료
        {
            System.out.println(answer);
            return;
        }
        str_arr = new String[N];
        arr = new ArrayList();
        arr_add = new ArrayList();
        arr_tmp = new ArrayList();
        arr.add('a' - 'a'); // arr에 기본 5개의 문자 저장
        arr.add('n' - 'a');
        arr.add('t' - 'a');
        arr.add('i' - 'a');
        arr.add('c' - 'a');
        int i, j, tmp;
        for(i = 0 ; i < N; i++)
        {
            str_arr[i] = br.readLine();
            for(j = 4; j < str_arr[i].length() - 4; j++) // anta와 tica를 제외한 중간 부분의 문자 저장
            {
                tmp = str_arr[i].charAt(j) - 'a';
                if(!arr.contains(tmp) && !arr_add.contains(tmp))
                    arr_add.add(tmp);
            }
        }
        Solve(0, 0);
        System.out.println(answer);
    }
    
    public static void Solve(int idx, int cnt)
    {
        int i, j, k, tmp;
        if(cnt == K - 5) // arr_tmp 크기가 K-5개라면
        {
            int count = 0;
            for(j = 0; j < N; j++)
            {
                for(k = 4; k < str_arr[j].length() - 4; k++) // 각 문자열의 중간값이 기본 문자나 arr_tmp에 포함되는지 확인
                {
                    tmp = str_arr[j].charAt(k) - 'a';
                    if(!arr.contains(tmp) && !arr_tmp.contains(tmp))
                    break;
                }
                if(k == str_arr[j].length() - 4) // 모든 문자가 포함되었다면 count 증가
                    count++;
            }
            answer = Math.max(answer, count); // answer과 count 중 큰 값 저장
        }
        for(i = idx; i < arr_add.size(); i++) // arr_tmp에 arr_add에 있는 문자들을 순서대로 저장
        {
            arr_tmp.add(arr_add.get(i));
            Solve(i + 1, cnt + 1);
            arr_tmp.remove(arr_tmp.size() - 1);
        }
    }
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

반례 좀 찾아주세요ㅠㅠ

06dyk26 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말