토니의 연습장

문제 7 3 8 8 1 0 2 7 4 44 5 2 6 5위 그림은 크기가 5인 정수 삼각형의 한 모습이다.맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.입력첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. 출력첫째 줄에 합이 최대..

문제수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.입력첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)출력첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.  아래에서는 가장 긴 증가하는 부분 수열(LIS; Longest Increasing Subsequence)을 구하는 전형적인 동적 프로그래밍(DP) 풀이 방법(O(N^2) 접근)과 그 과정에 대해 상세히 설명하고..

https://www.acmicpc.net/problem/2559N, K = list(map(int, input().split()))A = list(map(int, input().split()))# 누적합psum = [0]*Npsum[0] = A[0]for i in range(1,N): psum[i] = psum[i-1]+A[i] # 연속된 K일 온도합temp_sum = []for i in range(0,N-K+1): # i ~ i+K-1 if i==0: sum=psum[i+K-1] else: sum=psum[i+K-1]-psum[i-1] temp_sum.append(sum)print(max(temp_sum)) https://www...

https://www.acmicpc.net/problem/11399 두 가지 주요사항:1. 무엇을 선택할지 : 각 순서에 누구를 배치할지2. 어떤 순서로 선택할지 : 앞 또는 뒤에서부터 누구를 배치할지 -> 뒤에서부터 배치N = int(input())P = list(map(int, input().split()))P = sorted(P)total = 0for i in range(N): total += sum(P[:i+1]) print(total) https://www.acmicpc.net/problem/2847  두 가지 주요사항:1. 무엇을 선택할지 : 각 레벨의 보상을 몇으로 할지2. 어떤 순서로 선택할지 : 높은 레벨부터 보상 값을 결정하는 방향 N = int(input())L = [0]*..

https://www.acmicpc.net/problem/2003 N, M = map(int,input().split())A = list(map(int, input().split()))# 1. 합 = M : 시작점을 +1start = 0end = 0sum = A[0]count = 0while True: # 현재 구간 합이 M인지 확인 if sum == M: count += 1 # 구간 업데이트 if sum >= M: start += 1 sum -= A[start-1] else: if end == N-1: # 끝점 +1 하려는데 구간 종료될 상황이라면 break end += 1 ..

https://www.acmicpc.net/problem/2309from itertools import combinationsheights = []for _ in range(9): height = int(input()) heights.append(height) for a in combinations(heights, 7): if sum(a) == 100: a = list(a) # tuple은 sort 불가하여 list로 먼저 변환 a.sort() for x in a: print(x) break https://www.acmicpc.net/problem/10819 from itertools import permutati..

https://www.acmicpc.net/problem/1946 import sysinput = sys.stdin.readline # 입력 빠르게 받기 위한 세팅T = int(input())for _ in range(T): N = int(input()) candidates = [] for _ in range(N): s, m = map(int, input().split()) candidates.append((s,m)) # (s,m) candidates.sort() # 첫 번째 인자 기준 먼저 정렬, 같을 경우 두 번째 인자 기준 정렬됨 # but 문제 조건상 동석차 없음 top_ranking = 1e9 # 현재까지..

https://www.acmicpc.net/problem/2512 찾고자 하는 값 : 최적의 상한액탐색 범위 : [ 0, 지방 요청 금액 중 최댓값 ]시뮬레이션 : [ 0, 150 ] -> [ 75, 150 ] -> ...N = int(input())jibang = list(map(int, input().split()))budget = int(input())left = 0right = max(jibang)answer = -1while left  https://www.acmicpc.net/problem/2343  # 탐색하려는 값 : 블루레이의 용량# 탐색 볌위 : [ 영상길이의 최댓값, 영상길이의 합 ]N, M = map(int, input().split())running_time = list(map(i..