느낌표 공장

n, k = map(int, input().split()) # 동전 종류 수 n, 만들 가치의 합 k coins = [int(input()) for _ in range(n)] cnt = 0 # 총 사용한 동전 개수 for i in range(n-1, -1, -1): # 큰수부터 시작 if k < coins[i]: # k보다 동전이 크면 pass continue # 동전이 k보다 작은 경우 temp = k // coins[i] # i번째의 동전으로 만들 수 있는 최대 수 k -= coins[i] * temp # i번째의 동전으로 만들 수 있는 가치만큼 빼준다. cnt += temp # 방금 사용한 동전 수를 cnt에 합쳐준다. if not k: # k가 0이 되면 중단 break print(cnt) 큰 동..

n = int(input()) dp = [0 for _ in range(n+1)] for i in range(2, n+1): dp[i] = dp[i-1] + 1# 1번 if i % 3 == 0:# 2번 dp[i] = min(dp[i], dp[i//3]+1) if i % 2 == 0:# 3번 dp[i] = min(dp[i], dp[i//2]+1) print(dp[n]) dp 리스트 안의 i 자리에는 숫자 i를 1로 만들기 위한 주어진 연산을 사용하는 횟수의 최솟값이 담기게 된다. 따라서 2부터 시작하여 (1은 연산할 필요가 없으므로 0) n까지 저장하는 dp를 이용하여 문제를 풀어야 한다. dp[i]에 이전의 숫자(i-1)에서 구한 연산 사용 횟수 +1을 저장한다. 예) i = 10이라면 dp[9] = 2..

n = int(input()) cards = [0] + list(map(int, input().split())) dp = [0 for _ in range(n+1)] # 각 자리에는 카드 i개를 구매하는 최대 가격이 저장됨 for i in range(1, n+1): for j in range(1, i+1): # i가 4면 (3, 1), (2, 2), (1, 3)일 때를 보는것 dp[i] = max(dp[i-j] + cards[j], dp[i]) # i개 구매할때의 최대 가격 갱신 print(dp[n]) 풀이 포인트 dp 리스트의 자리 i에는 카드 i개를 구매하는 최대 가격이 저장된다. 이중 for문을 돌면서 카드 i개를 구매하는 경우, j가 1부터 돌면서 dp[i-j] + cards[j] 의 값들 중, 최..

n = int(input()) # 수열의 크기 numbers = list(map(int, input().split())) # 수열 dp = [0 for _ in range(n)] # dp 배열 answer = -1001 # 주어진 수열의 원소 범위보다 더 작게 설정 for i in range(n): dp[i] = max(dp[i-1] + numbers[i], numbers[i]) # 이전까지의 연속 합 vs 현재 숫자 (현재 숫자 택하면 꼬리자르기) answer = max(dp[i], answer) # 현재까지의 합이 더 크다면 answer 갱신 print(answer)

n = int(input()) # 수열의 크기 numbers = list(map(int, input().split())) # 수열 dp = [1 for _ in range(n)] # dp 배열 만들기 (자기자신 1이니까 1로 초기화) answer = 1 # 가장 긴 증가하는 부분 수열 길이 for i in range(n): for j in range(i): # 현재 위치(i)보다 전의 숫자(j)가 작은지 확인 if numbers[j] < numbers[i]: dp[i] = max(dp[i], dp[j]+1) # 결국 i위치의 이전 길이중 최댓값에 +1 하게 된다 answer = max(dp[i], answer) # 가장 긴 이라고 했으니, 길어졌다면 큰 값으로 갱신 print(answer)

n = int(input()) # 계단의 수 stairs = [int(input()) for _ in range(n)] # 계단 if n == 1: print(stairs[0]) else: dp = [0 for _ in range(n)] dp[0] = stairs[0] # 1번 계단 dp[1] = stairs[0] + stairs[1] # 1번 + 2번 계단 밟음 for i in range(2, n): # 1. 현재 계단 + 이전의 계단 + 전전전의 계단 밟은 경우 # 2. 현재 계단 + 전전의 계단 밟은 경우 # 두 경우 중 더 큰 값을 선택 dp[i] = max(dp[i-3] + stairs[i-1] + stairs[i], dp[i-2] + stairs[i]) print(dp[n-1]) 점화식을 찾는..

import sys input = sys.stdin.readline n, m = map(int, input().split()) # 수의 개수 n, 합을 구해야 하는 횟수 m numbers = list(map(int, input().split())) # n개의 수 # dp 리스트 만들기 dp = [0 for _ in range(n+1)] for i in range(n): dp[i+1] = dp[i] + numbers[i] for _ in range(m): i, j = map(int, input().split()) print(dp[j] - dp[i-1]) 풀이 먼저 dp[i+1]에 numbers[i]까지(numbers[:i+1])의 합을 저장하여 dp리스트를 만든다. i와 j가 주어졌을 때, i는 구간의 시..

n = int(input()) arr = [0 for _ in range(1000001)] arr[1] = 1 arr[2] = 2 for i in range(3, n+1): # 더해서 저장하고 마지막에 나머지 구하면 숫자가 너무 커지니, 나머지로 넣어준다. arr[i] = (arr[i-1] + arr[i-2]) % 15746 print(arr[n]) 규칙 : 크기가 n일 때의 가짓수 = 크기가 n-1일 때의 가짓수 + 크기가 n-2일 때의 가짓수

탑다운 방식 (재귀) tc = int(input()) dp_l = [0, 1, 2, 4] + [0 for _ in range(9)] # 11까지의 방법을 담을 리스트 # 규칙 : 정수 n을 1, 2, 3으로 나타낼 수 있는 방법 수 = 정수 n-3 , n-2, n-1 을 나타낼 수 있는 방법 수를 다 더한 것 # dp 함수 def dp(n): # 리스트에 현재 n을 나타낼 수 있는 방법의 수가 비어 있다면 if not dp_l[n]: # 정수 n-1의 방법의 수가 저장되어 있는지 확인 -> 안되어있다면 또 들어감 dp(n-1) # n-1까지 다 저장되어 있으면 현재 n의 정수를 나타낼 수 있는 방법의 수 저장. dp_l[n] = dp_l[n-3] + dp_l[n-2] + dp_l[n-1] for i in..

n = int(input()) arr = [0 for _ in range(101)] arr[1] = 1 arr[2] = 1 arr[3] = 2 for i in range(3, n+1): # 규칙 : 현재 수 = 전의 수 + 전전 수 arr[i] = arr[i-1] + arr[i-2] print(arr[n])