글 읽기 - 1020번시간초과질문입니다ㅠㅠ

sdfgcsdfgc 5년 전 0

다음과같이 했는데 시간초과문제를 어떻게해결해야할지 잘모르겟습니다 .ㅠㅠ

public class _1020 {

	static int line[] = { 6,2,5,5,4,5,6,3,7,5};
	static String init;
	public static void main(String[] args) throws IOException {
    
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		init = br.readLine();
		int start = totalline(init);
		int count=0;
	
		for(long next=Long.parseLong(init)+1; ; next++) {
				count++;
				String nextString = Long.toString(next);
				int end = totalline(nextString);
				if(start == end) {
					break;
				}
			}
			
			System.out.println(count);
	
	}
	
	public static int totalline(String input) {
		int totalLinesegment =0;
		totalLinesegment += (init.length() - input.length()) *6;

		for(int i=0; i<input.length(); i++) {
			totalLinesegment +=line[input.charAt(i)-48];
		}
		return totalLinesegment;
		
	}

}

djm03178 5년 전 0

15자리나 되기 때문에 1씩 세는 단순한 방법으로 풀 수 없습니다. 매 자리마다 부분합을 이용한 dp를 해야 하는, 매우 구현이 까다로운 문제입니다.

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

문제

문제

출처

ICPC

1020번시간초과질문입니다ㅠㅠ

sdfgcsdfgc 5년 전 0

djm03178 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말