🥦 1535. 안녕
문제
세준이는 성형수술을 한 후에 병원에 너무 오래 입원해 있었다. 이제 세준이가 병원에 입원한 동안 자기를 생각해준 사람들에게 감사하다고 말할 차례이다.
세준이를 생각해준 사람은 총 N명이 있다. 사람의 번호는 1번부터 N번까지 있다. 세준이가 i번 사람에게 인사를 하면 L[i]만큼의 체력을 잃고, J[i]만큼의 기쁨을 얻는다. 세준이는 각각의 사람에게 최대 1번만 말할 수 있다.
세준이의 목표는 주어진 체력내에서 최대한의 기쁨을 느끼는 것이다. 세준이의 체력은 100이고, 기쁨은 0이다. 만약 세준이의 체력이 0이나 음수가 되면, 죽어서 아무런 기쁨을 못 느낀 것이 된다. 세준이가 얻을 수 있는 최대 기쁨을 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 사람의 수 N(≤ 20)이 들어온다. 둘째 줄에는 각각의 사람에게 인사를 할 때, 잃는 체력이 1번 사람부터 순서대로 들어오고, 셋째 줄에는 각각의 사람에게 인사를 할 때, 얻는 기쁨이 1번 사람부터 순서대로 들어온다. 체력과 기쁨은 100보다 작거나 같은 자연수 또는 0이다.
출력
첫째 줄에 세준이가 얻을 수 있는 최대 기쁨을 출력한다.
예제 입력 1
3
1 21 79
20 30 25
예제 출력 1
50
예제 입력 2
1
100
20
예제 출력 2
0
예제 입력 3
8
100 15 1 2 3 4 6 5
49 40 1 2 3 4 5 4
예제 출력 3
59
예제 입력 4
4
100 50 20 13
20 30 40 50
예제 출력 4
120
예제 입력 5
8
100 26 13 17 24 33 100 99
34 56 21 1 24 34 100 99
예제 출력 5
135
예제 입력 6
12
1 1 1 1 1 1 1 1 1 1 1 1
100 100 100 100 100 100 100 100 100 100 100 100
예제 출력 6
1200
알고리즘 분류
- 다이나믹 프로그래밍
- 브루트포스 알고리즘
- 배낭 문제
코드 - python3 성공
import sys
input = sys.stdin.readline
N = int(input()) # 사람 수
L = [int(x) for x in input().split()] # 체력
J = [int(x) for x in input().split()] # 기쁨
L, J = [0] + L, [0] + J # 0을 추가하여 인덱스 계산을 편리하게 한다.
dp = [[0 for _ in range(101)] for _ in range(N+1)] # j 체력을 사용했을 때 얻을 수 있는 최대 기쁨
for i in range(1, N+1): # 사람
for j in range(1, 101): # 체력
if L[i] <= j: # 이 사람을 선택할 경우와 선택하지 않을 경우
dp[i][j] = max(dp[i-1][j], dp[i-1][j-L[i]] + J[i])
else: # 체력을 초과할 경우
dp[i][j] = dp[i-1][j]
print(dp[N][99]) # 최대 체력에서 얻을 수 있는 최대 기쁨🥦 2205. 저울 추 만들기
문제
질량(또는 무게)가 1, 2, 3, …, n인 납덩어리가 있고, 질량이 1, 2, 3, …, n인 주석덩어리가 있다. 각각의 질량을 갖는 덩어리들은 1개씩밖에 없다. 이제 이 납덩어리와 주석덩어리를 한개씩 녹여 합쳐서 질량이 2의 거듭제곱이 되는 저울추를 n개 만들려고 한다.
질량이 x인 납덩어리와 질량이 y인 주석덩어리를 합친 경우를 (x, y)로 나타내기로 하고, 다음과 같이 녹여 합친 경우를 보자. (1, 1), (2, 2), (3, 5), (4, 4), (5, 3). 각각의 저울추의 질량은 2, 4, 8, 8, 8이 되고 이들은 모두 2의 거듭제곱 꼴이 된다.
n이 주어졌을 때 저울추 n개를 만드는 방법을 하나 구하는 프로그램을 작성하시오.
입력
첫째 줄에 n(1 ≤ n ≤ 10,000)이 주어진다.
출력
첫째 줄부터 각 줄에 질량이 1인 납덩어리와 합친 주석덩어리의 질량, 질량이 2인 납덩어리와 합친 주석덩어리의 질량, 질량이 3인 납덩어리와 합친 주석덩어리의 질량, …을 n개의 줄에 출력한다.
예제 입력 1
5
예제 출력 1
1
2
5
4
3
알고리즘 분류
- 수학
- 그리디 알고리즘
코드 - python3 성공
import sys
input = sys.stdin.readline
n = int(input())
check = [] # 제곱 수 저장
idx = 2 # 제곱 수 생성
while True:
if idx <= (2*n)+1: # 2의 거듭제곱 수 중에서 n보다 작거나 같은 값만 check에 저장
check.append(idx)
else:
break
idx *= 2
ir = [0 for i in range(0,n+1)] # 주석 질량
ir[0] = 1
for i in range(len(ir)-1,0,-1): # 주석 질량 역순환
for k in range(0,len(check)): # 제곱수 길이만큼 순환
if check[k] - i <= n and check[k] > i: # 제곱수에서 주석을 뺀값이 갯수보다 작고, 제곱수가 주석질량보다 클 때
if ir[i] == 0 and ir[check[k]-i] == 0: # 주석 질량이 0이거나 제곱수에서 뺀 값이 0 일때 해당 주석 저장
ir[i] = check[k] - i
ir[check[k]- i] = i
break
for i in range(1,len(ir)):
print(ir[i]) # 주석의 질량🥦 13398. 연속합 2
문제
n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다. 또, 수열에서 수를 하나 제거할 수 있다. (제거하지 않아도 된다)
예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 수를 제거하지 않았을 때의 정답은 12+21인 33이 정답이 된다.
만약, -35를 제거한다면, 수열은 10, -4, 3, 1, 5, 6, 12, 21, -1이 되고, 여기서 정답은 10-4+3+1+5+6+12+21인 54가 된다.
입력
첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.
출력
첫째 줄에 답을 출력한다.
예제 입력 1
10
10 -4 3 1 5 6 -35 12 21 -1
예제 출력 1
54
알고리즘 분류
- 다이나믹 프로그래밍
코드
import sys
input = sys.stdin.readline
N = int(input())
input_array = list(map(int, input().split()))
dp = [[x for x in input_array] for _ in range(2)] # 누적합 계산
for i in range(1, N):
dp[0][i] = max(dp[0][i - 1] + input_array[i], dp[0][i]) # 누적합 비교 최댓값 도출
dp[1][i] = max(dp[0][i - 1], dp[1][i - 1] + input_array[i]) # 수를 하나 제거했을 때 최댓값
print(max(max(dp[0]), max(dp[1])))