다이나믹 프로그래밍 알고리즘 Q www.acmicpc.net/problem/13301 13301번: 타일 장식물 대구 달성공원에 놀러 온 지수는 최근에 새로 만든 타일 장식물을 보게 되었다. 타일 장식물은 정사각형 타일을 붙여 만든 형태였는데, 한 변이 1인 정사각형 타일부터 시작하여 마치 앵무조개 www.acmicpc.net A 다이나믹 프로그래밍을 이용하여 풀었다. 피보나치 수열인 것을 파악하면 쉽다. 코드 n = int(input()) d = [0] * 81 d[0] = 4 d[1] = 6 for i in range(2, n+1): d[i] = d[i-1] + d[i-2] print(d[i - 1])
다이나믹 프로그래밍 알고리즘 Q www.acmicpc.net/problem/9625 9625번: BABBA 상근이는 길을 걷다가 신기한 기계를 발견했다. 기계는 매우 매우 큰 화면과 버튼 하나로 이루어져 있다. 기계를 발견했을 때, 화면에는 A만 표시되어져 있었다. 버튼을 누르니 글자가 B로 변했 www.acmicpc.net A 다이나믹 프로그래밍을 이용하여 풀었다. 주의할 점은 문자열이기 때문에 단순히 풀면 메모리초과가 일어날 수 있다. A와 B가 각자 피보나치 수열을 따른다는 것을 이용하여 풀어야 한다. 코드 k = int(input()) #정수 입력 d = [0] * 46 #DP 테이블 초기화 d[0] = 0 d[1] = 1 c = [0] * 46 #DP 테이블 초기화 c[0] = 0 c[1] = ..
다이나믹 프로그래밍 알고리즘 Q www.acmicpc.net/problem/10870 10870번: 피보나치 수 5 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net A 입력조건만 조심해서 풀면 된다. 코드 n = int(input()) d = [0] * 21 d[0] = 0 d[1] = 1 d[2] = 1 for i in range(3, n+1): d[i] = d[i-1] + d[i-2] print(d[n])
다이나믹 프로그래밍 알고리즘 Q www.acmicpc.net/problem/2748 2748번: 피보나치 수 2 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net A 다이나믹 프로그래밍을 이용하여 풀었다. 코드 n = int(input()) d = [0] * 91 d[1] = 1 d[2] = 1 for i in range(3, n+1): d[i] = d[i-1] + d[i-2] print(d[n])
