글 읽기 - 1120번 시간초과 ㅠㅠㅠ도와주세요

roskeo 2년 전 0

아직 자구랑 알고 안들어갓는데

이 문제 시간초과 안나게 더 짧게 하는 법 잇을까요?

(자구든 알고든 상관없어요 ㅠㅠ 반복문을 너무 많이 써서 그런것 가튼데

어디서 줄여야 될까요.)

제 아이디어는 이겁니다.

abbaaba

abaa

이렇게 입력받아서 배열에 집어넣고

둘의 길이의 차이만큼 문자를 더 입력받는다고 생각합니다.

뒤에 문자를 붙일때는 두 문자열의 차이가 변하지 않습니다(어차피 같은 알파벳을 붙일거니까요)

앞에 문자를 붙일때만을 신경써서 'abaa' 이 네글자가 오른쪽으로 몇칸 움직여야 abbaaba랑 가장 차이가 안나는지 계산하는 겁니다

(앞에 붙이는 문자가 만드는 차이는 생각할 필요가 없습니다. 어차피 차이가 최소가 되어야 하니까요.)

더 간단하고 번뜩이는 아이디어가 없을까요? 아니면 시간초과가 안되게 하는 기술좀 알려주세요 ㅠㅠ!!

											#include <stdio.h>
#include <string.h>
 
int main(){
    int cnt = 0;
    int i = 0;
    int j = 0;
    int min = 100;
    int str;
    char sh[50];
    char lng[50];
     
    scanf("%s", sh);
    scanf("%s", lng);
     
    str = strlen(lng) - strlen(sh);
     
    for(i = 0 ; i < str ; i ++)
    {
        while(sh[j] != '\0')
        {
         if(sh[j] != lng[i+j])
         {
             cnt++;
             j++;
         }
             
            if(min >= cnt)
                min = cnt;
             
             
        }
         
        printf("%d", min);
        return 0;
    }
}
										

ZZangZZang 2년 전 0

두 문자가 같으면 j++이 안되서 while문에서 뱅뱅 도네요....

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

문제

문제

출처

ACM-ICPC

1120번 시간초과 ㅠㅠㅠ도와주세요

roskeo 2년 전 0

ZZangZZang 2년 전 0

Baekjoon Online Judge

채점 현황

문제

출처

ACM-ICPC

Coder's High

앱