글 읽기 - 1543 문제 해결 방식에 대한 고민

simsimjae 5년 전 0

이문제에 정답은 앞에서부터 순차적으로 검색을 하는게 최대 단어의 개수를 세는 그리디한 방법인것 같은데

이 문제를 보고 그리디한 방법으로 풀릴것 같다는 판단을 어떤 논리적인 생각에 따라 하게 되는 건지 궁금합니다!

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    private static int n;
    private static int cnt;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String doc = sc.nextLine();
        String str = sc.nextLine();
        int cnt = 0;
        int size = doc.length();
        int size2 = str.length();
        for(int i=0; i<=size-size2; i++){
            String temp = doc.substring(i,i+size2);
            if(temp.equals(str)) {
                cnt++;
                i+=size2-1;
            }
        }
        System.out.println(cnt);

    }


}

cleankid99 3년 전 0

저도 문제를 보고 그리디인가 아니면 최적의 해가 따로 있을까 라는 고민을 먼저 했습니다.

그러나 예제 1번의 경우 ababababa / aba 를 따져보면

1. aba , b, aba, ba

2. ab, aba, b, aba

3. abab, aba, ba

여기서 1과 3의 경우를 보는 순간에 직감했습니다. 최적의 해는 그리디로 풀어야한다는걸요

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

문제

문제

출처

ICPC

1543 문제 해결 방식에 대한 고민

simsimjae 5년 전 0

cleankid99 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말