21923번: 곡예 비행동헌이는 모형 비행기 조종 대회에 참가하였다. 이 대회에서는 격자 모양의 공간에서 모형 비행기를 조종하여 얻는 비행 점수로 순위를 매긴다. 격자의 각 칸에는 점수가 부여되어 있고, 비행www.acmicpc.net 코드n, m = map(int, input().split())scores = [[0]+list(map(int, input().split())) for _ in range(n)]up = [[-int(1e9)]*(m+1) for _ in range(n+1)] # 상승 비행 점수down = [[-int(1e9)]*(m+1) for _ in range(n+1)] # 하강 비행 점수up[n-1][1] = scores[n-1][1] # 출발점# 상승for j in range..
dynamicprogramming
15993번: 1, 2, 3 더하기 8첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 100,000보다 작거나 같다.www.acmicpc.net 코드dp = [[0]*2 for _ in range(100001)] # 홀수, 짝수dp[1][0] = 1dp[2][0] = 1dp[2][1] = 1dp[3][0] = 2dp[3][1] = 2for i in range(4, 100001): dp[i][0] = (dp[i-1][1]+dp[i-2][1]+dp[i-3][1]) % 1_000_000_009 dp[i][1] = (dp[i-1][0]+dp[i-2][0]+dp[i-3][0]) % 1_000_000_009for _ in ..
2157번: 여행첫째 줄에 N(1 ≤ N ≤ 300), M(2 ≤ M ≤ N), K(1 ≤ K ≤ 100,000)가 주어진다. K는 개설된 항공로의 개수이다. 다음 K개의 줄에는 각 항공로에 대한 정보를 나타내는 세 정수 a, b, c(1 ≤ a, b ≤ N, 1 ≤ c ≤ 1www.acmicpc.net 코드import sysinput = sys.stdin.readlinen, m, k = map(int, input().split())path = [[-1]*(n+1) for _ in range(n+1)] # path[i][j] : i->j로 갈 때 기내식 점수for _ in range(k): a, b, c = map(int, input().split()) if ..
1757번: 달려달려 어제, 그리고 어제 어제 단체달리기를 두 번이나 하였다. 원장선생님의 이러한 하드 트레이닝으로 월드 학생들의 체력은 거의 박지성 수준이 되었다. 그래서 월드 학생들은 운동장을 도는데 정 www.acmicpc.net 코드 n, m = map(int, input().split()) d = [0]+[int(input()) for _ in range(n)] dp = [[0]*(m+1) for _ in range(n+1)] # i분에 지침 지수가 j일 때 최대 이동 거리 for i in range(1, n+1): dp[i][0] = max(dp[i-1][0], dp[i][0]) # 지침 지수 0에서 계속 쉬는 경우 for j in range(1, m+1): if j == 1 or dp[i-1..
2670번: 연속부분최대곱 첫째 줄은 나열된 양의 실수들의 개수 N이 주어지고, 그 다음 줄부터 N개의 수가 한 줄에 하나씩 들어 있다. N은 10,000 이하의 자연수이다. 실수는 소수점 첫째자리까지 주어지며, 0.0보다 크거나 www.acmicpc.net 코드 n = int(input()) lst = [float(input()) for _ in range(n)] for i in range(1, n): lst[i] = max(lst[i], lst[i]*lst[i-1]) print("{:.3f}".format(max(lst))) 실수를 입력받았던 lst에 다이나믹 프로그래밍을 그대로 적용한다. lst가 i번째까지의 곱의 최댓값을 담는 배열이 된다. 이어지는 수열이 현재의 값보다 큰 경우, 즉 lst[i]..
