본문 바로가기
728x90

전체 글74

다이나믹 프로그래밍 - 백준 2193 [Python] Problem) https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net Solution) D[i][j] = i 자리 이친수의 개수 중에서 j로 끝나는 것의 개수 (j=0,1) 가능한 경우는 0으로 끝나는 경우 (D[i][j]) 앞에 0과 1이 올 수 있다. D[i-1][0] + D[i-1][1] 1로 끝나는 경우 (D[i][1]) 앞에 1은 올 수 없다. 즉, 0만 올 수 있다. D[i-1][0] Answer) n = int(input()).. 2021. 8. 5.
다이나믹 프로그래밍 - 백준 10844 [Python] Problem) https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net Solution) 연속하는 수의 차이, 마지막에 오는 수의 차이를 기록하면 된다. 따라서 1차원으로 바로 정의하기 보다는 D[i][j] = 길이가 i인 계단 수, 마지막 자리가 j인 개수로 정의하여 해결한다. 그리고 맨 마지막에 올 수 있는 수는 j-1이거나, j+1인 경우이기 때문에 각각 나눠서 풀도록 한다. Answer) mod = 1000000000 n = int(input()) d = [[0]*10 for _ in range(101)] for i in range(1, 10): d[1][i.. 2021. 8. 5.
다이나믹 프로그래밍 - 백준 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.
728x90

티스토리툴바