DP3 1904번 01타일(python3) https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 단순히 d[i] = d[i - 1] + d[i - 2]의 점화식을 적용해서 문제를 해결하면 된다. data = [0] * 1000001 data[1] = 1 data[2] = 2 data[3] = 3 N = int(input()) for i in range(4, N + 1): data[i] = (data[i-1] + data[i-2]) % 15746 print(data[N]) 2022. 2. 2. 1309번 동물원(python3) https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net dp를 적용해주면 된다. 처음에는 dp테이블을 하나만 설정해서 해결하는 방법을 찾았지만 해결하지 못했다. 그래서 dp테이블을 세개로 나누어서 문제를 풀었다. N = int(input()) no_data = [0] * 100001 left_data = [0] * 100001 right_data = [0] * 100001 no_data[0] = 1 for i in range(1, N + 1): no_data[i] = left_data[i - 1] + right_data[i - 1] + no_data[i - 1] left_data[i].. 2022. 2. 2. 이.코.테 바닥공사, 효율적인 화폐 구성(python3) 바닥공사 코드(p. 223) N = int(input()) data = [0] * 1001 data[1] = 1 data[2] = 3 for i in range(3, N + 1): data[i] = (data[i - 1] + 2 * data[i - 2]) % 796796 print(data[N]) 간단한 dp 문제이다. 효율적인 화폐 구성(p. 226) N, M = map(int, input().split()) money = [] for i in range(N): money.append(int(input())) data = [0] * 10001 for i in money: data[i] = 1 for i in range(money[len(money) - 1] + 1, M + 1): ans = 10001 .. 2022. 1. 25. 이전 1 다음