728x90 반응형 동적계획법2 [백준/Python] 9461 파도반 수열 문제: https://www.acmicpc.net/problem/9461 사용 알고리즘: DP 입력첫째 줄에 테스트 케이스의 개수 TN (1 ≤ N ≤ 100) 첫 삼각형은 정삼각형으로 변의 길이는 1다음과 같은 과정으로 정삼각형을 계속해서 추가할 때 나선에서 가장 긴 변의 길이 찾기 이 문제는 그림을 보고 규칙을 찾아서 쉽게 풀 수 있었다. P(1) = 1P(2) = 1P(3) = 1P(4) = 2P(5) = 2P(6) = P(5) + P(1)P(7) = P(6) + P(2)P(8) = P(7) + P(3)P(9) = P(8) + P(4)P(10) = P(9) + P(5) 점화식을 써보면-> P(n) = P(n-1) + P(n-5) 인덱스 1부터 사용할거라 0번 인덱스에는 0을, 1~5번 인덱.. 2024. 7. 11. [백준/Python] 2839 설탕 배달 문제: https://www.acmicpc.net/problem/2839 사용 알고리즘: DP 상근이가 설탕을 정확하게 N kg 배달해야 한다. 이 때 설탕은 3kg, 5kg 두 가지 봉지에 담겨져 있다. 상근이가 설탕을 정확하게 N kg 배달해야할 때 최소 봉지의 개수를 구하는 프로그램 구현 입력N (3 출력상근이가 배달하는 봉지의 최소 개수 출력, 만약 정확하게 N kg 을 맞출 수 없다면 -1 출력 - 인덱스 1부터 사용할 것이기 때문에 dp 배열의 길이를 (n+1) 로 만들고, 기본 값을 -1 로 초기화- n 의 값이 5 이상인 경우와 아닌 경우를 나누어 초기화 시킴 (n 이 3, 4 인 경우 dp[5] 를 먼저 초기화 시키면 인덱스 에러남)# 입력받기n = int(input())# dp .. 2024. 7. 4. 이전 1 다음 728x90 반응형
