처음 접근을 그리디로 접근을 했어서 답이 틀렸었다.dp로 풀면 간단하게 풀리는 문제였다.dp로 현재값 - arri , 10원이 현재값이면 10원 - 현재동전값이 3원 이면 7원 일때 개수 +1 아니면 10원을 전에 만들었던 값과 비교해서min을 사용해서 더 작을것을 선

res1 에는 i번째를 선택하지 않거나 전에 뺀것중에서 최대값 res1 에서 arri 를 더한것 중에 최대값을 넣게된다.이해하는데 엄청 오래걸렸다..나는 빡빡이다

res 배열 인덱스에는 그 당시 최댓값이 들어가있다2중 for문을 사용하여서 resj + resi-j , 즉그 인덱스에서는 최선의 선택을 한 값 두개를 더했을때 또는arri 한개만 선택했을경우 중에 최대값을 resi 에 저장함아직 dp에 대한 이해가 많이 부족한것같다문

문제

arr = 입력받은값res = 현재위치에 올수있는 최소 횟수비교조건으로는 i + 0 ~ arri의값이 < n 보다 작고i+j ,즉 j가 0 이 아닐경우 그리고 resi , 현재위치에 올수 없었던 경우 가 아니면resi+j == 0 이면 처음 도착했기때문에 resi

이 문제는 링크로 대체..참고 블로그a = 1일때 예외처리를 잘못해서 30분이나 날렸다...화가나는 문제..

점화식이 arri-1 + arri-2 + arri-3 이 나왔는데문제를 다 풀었는데 메모리초과가 나와서 검색을 해보니arri -1 을 더할때 % 1,000,000,009 을 해주니 메모리 초과가 안났다.전에 풀었던 1,2,3 더하기와 비슷해서 금방 풀었지만메모리 초과가

nCr 을 구하는 공식은 위에 사진과 같다dp를 사용해서 1~n까지 팩토리얼을 모두 구한뒤그 값을 활용해서 nCr 공식을 사용함그냥 간단하게 공식만 사용한 문제였던것 같다..큰고민없이 풀었다..

res 는 연속으로 선택했을경우 가장 큰 값arr 는 입력받은 값n의 값이 1보다 같거나 클 경우라서 n = 1 , n = 2 예외로 처리해두고n 이 3보다 같거나 클 경우경우의 수 3가지 resi-1 + arri 를 선택했을때arri 만 선택했을때arri-1 + a

1자리수 계단수는 1,2,3,4,5,6,7,8,9 총 9 개가 있다0으로 시작하는 수는 없기에 맨 앞자리가 0 인경우 , 즉 01 , 012 등은계단수가 아니다.간단하게 규칙을 보면 배열에서 dpi , i는 자리수 n은 0~9까지dpi = dpi-1 + dpi-1 이라

bisect정렬된 배열에서 특정 원소를 찾을때 사용bisect_left(a, x)\-> 정렬된 순서를 유지하면서 리스트 a 에서 삽입할 x의 가장 왼쪽 인덱스arri 가 dp의 마지막 원소 즉 앞에 봤던 원보다 가장 클 경우dp에 마지막 위치에 추가함arri 가 dp의