흙금이네 블로그

아이디어 문자열의 접두사와 접미사가 일치하면서 문자열 중간에 등장하는 가장 긴 부분 문자열을 찾는다. 풀이 숫자 0~9는 성냥개비 2~7개로 모두 표현할 수 있다. 리스트 M에 인덱스만큼의 성냥개비로 만들 수 있는 가장 작은 수를 저장한다. 리스트 dp에 인덱스 7까지는 M과 같은 값들을 저장하고, 인덱스 8에는 10을 저장하여 for문이 9부터 시작하도록 한다. 인덱스 8을 이후 for문에서 접근하면 dp[8-7]로 dp[1]을 가리켜 값이 잘못 저장되기 때문이다. 성냥개비 2~7개마다 자릿수가 하나씩 늘어나므로 이전 수에서 자릿수를 늘려 만들 수 있는 가장 작은 수를 저장해 나간다. 성냥개비로 가장 큰 수를 만들기 위해서는 가능한 적은 성냥개비를 사용하여 자릿수를 크게 만드는 것이므로, 성냥개비 2개..