갓퍄쿠의 공부기록 갓퍄쿠의 공부기록

1, 2, 3 더하기알고리즘 - dynamic programming과정:n=1 : 1 -> 1n=2 : 1+1, 2 -> 2n=3 : 1+1+1, 1+2, 2+1, 3 -> 4n=4 : 1+1+1+1,1+1+2,1+2+1,1+3, 2+1+1, 2+2, 3+1 -> 7cnt = int(input())arr = [0, 1, 2, 4, 0, 0, 0, 0, 0, 0, 0] #n은 양수이며 11보다 작음for a in range(0,cnt): n = int(input()) for i in range(4,n+1): arr[i] = arr[i-1] + arr[i-2] + arr[i-3] print(arr[n])

2×n 타일링알고리즘 - dynamic programming 과정:그림을 그려가며 규칙을 찾아보았다.아래 그림과 같이 2xn 직사각형을 타일로 채울 수 있다.arr[2]=2arr[3]=3arr[4]=5arr[5]=8 ...arr[4]는 'arr[3]에 2x1 세로타일을 추가한 것 + arr[2]에 2개의 1x2 가로타일을 추가한 것' 이 된다.문제의 규칙은 arr[n] = arr[n-1] + arr[n-2] 이므로 이를 dp로 작성해보았다.n = int(input())arr = [1]*(n+1) #array 1로 초기화for i in range(2,n+1): arr[i] = arr[i-1] + arr[i-2]print(arr[n]%10007)

1로 만들기알고리즘 - dynamic programming 과정:처음에는 3으로 나눠질 수 있는 숫자는 3으로 나누기 -> 2로 나눠질 수 있는 숫자는 2로 나누기 -> 둘다 안되면 -1 로 풀어보려했지만 힌트를 보고 아닌것을 알게되었다.위와 같이 풀면 10 -> 5 -> 4 -> 2 -> 1 4번으로 더 연산이 많이 필요해진다.힌트를 참고하면X=10 : 10 -> 9 -> 3 -> 1X=9 : 9 -> 3 -> 1X=3 : 3 -> 1형태가 된다.n : 입력받은 정수 Narr[n] : 연산하는 횟수arr[i-1] +1 : 1을 뺀다 연산arr[i//3] +1 : 3으로 나누는 연산arr[i//2] +1 : 2로 나누는 연산'1을 뺀다 연산', '3으로 나누는 연산', '2로 나누는 연산' 을 적절히 사..