[백준/Python] 2805번: 나무 자르기
문제 https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 문제 요약 상근이는 N 그루의 나무를 절단기로 높이를 지정하고 잘라 M미터의 나무를 구하려고 한다. 예를 들어 한 줄에 연속해 있는 나무의 높이가 20, 15, 10, 17이라고 할 때, 상근이가 높이를 15로 지정했다면, 나무를 자른 뒤의 높이는 15, 15, 10, 15가 될 것이고 상근이는 길이가 5인 나무와 2인 나무를 구할 수 있다. 적어도 M..
[백준/Python] 15990번: 1, 2, 3 더하기 5
문제https://www.acmicpc.net/problem/15990 15990번: 1, 2, 3 더하기 5각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다.www.acmicpc.net문제 요약정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1000000009로 나눈 나머지를 출력한다. + 같은 수를 두 번 이상 연속해서 사용하면 안된다.코드T = int(input()) dp = [[0, 0, 0] for _ in range(100001)] # dp[i][0]: i를 1, 2, 3으로 나타낸 수 중 1로 끝나는 경우의 수 # dp[i][1]: i를 1, 2, 3으로 나타낸 수 중 2로 끝나는 경우의 수 ..