흙금이네 블로그

아이디어 동적 계획법으로 경우의 수를 더해 나간다. 풀이 가치 합을 인덱스로 하여 경우의 수를 저장하는 리스트 dp를 생성한다. k보다 큰 값은 고려할 필요가 없으므로 dp의 길이는 k+1로 하고, 인덱스 0의 값은 1, 나머지는 0으로 채운다. 인덱스 0의 값을 1로 채우는 이유는 이후 for문에서 동전 가치의 경우의 수를 증가시키기 위함이다. 차례로 입력 받은 동전의 가치 c로 c보다 더 작은 가치는 만들 수 없으므로 for문에서 가치 합을 c부터 시작한다. c 이상의 가치 합 j의 경우의 수 dp[j]에 j에서 c를 뺀 가치의 경우의 수 dp[j-c]를 더해 나간다. import sys input = sys.stdin.readline def solution(): n, k = map(int, inpu..

아이디어 표에서 조건에 맞게 칸을 이동하며 만들 수 있는 숫자들 중 가장 큰 완전 제곱수를 구한다. 풀이 #1 (Python) 표를 입력 받아 2차원 리스트 table에 저장하고, 만들 수 있는 숫자들을 저장하는 세트 numbers를 생성한다. 차례로 표의 i행 j열에 있는 숫자를 numbers에 추가하고, 행과 열의 공차 di, dj로 함수 make_number를 호출한다. 이때 행과 열의 공차가 모두 0이면 무한 루프에 빠지므로 둘 중 하나라도 0이 아닐 때 함수를 호출하도록 한다. 함수 make_numbers는 인덱스를 벗어나지 않는 범위에서 재귀 호출로 공차에 따라 칸을 이동하며 숫자를 이어 붙인다. 이어 붙인 숫자들을 numbers에 추가하며, 공차가 음수인 숫자들을 저장하기 위해 역순으로 이어..

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