728x90 코딩테스트25 다이나믹 프로그래밍 - 백준 15990 [Python] Problem) https://www.acmicpc.net/problem/15990 15990번: 1, 2, 3 더하기 5 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net Solution) 어떤 조건이 나타났을 때, 그 조건을 점화식에 넣어버리면 된다. 따라서, n-1로 끝났을 때 마지막에 어떤수를 사용했는지 정의하는 것을 추가해야 한다. D[i][j] = i를 1,2,3의 합으로 나타내는 방법의 수, 마지막에 사용한 수는 j i-1을 만든 경우 = D[i-1][2] + D[i-1][3] i-2를 만든 경우 = D[i-2][1] + D[i-2][3] i-3을 만든 경우 = D[i-3][1] + D[i.. 2021. 8. 5. 다이나믹 프로그래밍 - 백준 11052 [Python] Problem) https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net Solution) 가능한 방법의 갯수가 주어지지 않을 경우의 문제 - 변수를 사용해서 일반화를 한다. D[i] = 카드 i개 구매하는 최대 비용 가장 마지막에 올 수 있는 경우가 N가지 라고 할 수 있으며, N가지를 다 구해보고 최대 비용을 계산하면 된다. 카드 i개를 구매하는 방법 카드 1개가 들어있는 카드팩을 구매하고, 카드 i-1개를 구매 카드 2개가 들어있는 카드팩을 구매하고, 카.. 2021. 8. 4. 다이나믹 프로그래밍 - 백준 9095 [Python] Problem) https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net Solution) D[N] = D[N-1] + D[N-2] + D[N-3] 의 결과가 된다. 이때, D[0] 을 살펴봐야하는데, D[0]을 정의해야 편하게 코딩할 수 있다. 수를 0개 사용하는 경우는 합이 없는 경우 이므로 아무것도 사용하지 않는 경우, 1가지 이다. 따라서 D[0] = 1로 정의한다. Answer) d = [0]*11 d[0] = 1 for i in range(1, 11): if i-1 >= 0: d[i] += d[i-1] if i-2 >= 0: d[i] += .. 2021. 8. 4. 다이나믹 프로그래밍 - 백준 11726 [Python] Problem) https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net Solution) D[N] = D[N-1] + D[N-2] 이라는 점화식을 세워 해결하면 된다. Answer) n = int(input()) d = [0]*1001 d[1] = 1 d[2] = 2 for i in range(3,n+1): d[i] = d[i-1] + d[i-2] d[i] %= 10007 print(d[n]) 2021. 8. 4. 이전 1 2 3 4 5 6 7 다음 728x90