25년 간의 수행 끝에 원재는 미래를 보는 능력을 갖게 되었다. 이 능력으로 원재는 사재기를 하려고 한다.
다만 당국의 감시가 심해 한 번에 많은 양을 사재기 할 수 없다.
다음과 같은 조건 하에서 사재기를 하여 최대한의 이득을 얻도록 도와주자.
1. 원재는 연속된 N일 동안의 물건의 매매가를 예측하여 알고 있다.
2. 당국의 감시망에 걸리지 않기 위해 하루에 최대 1만큼 구입할 수 있다.
3. 판매는 얼마든지 할 수 있다.예를 들어 3일 동안의 매매가가 1, 2, 3 이라면 처음 두 날에 원료를 구매하여 마지막 날에 팔면 3의 이익을 얻을 수 있다.
[입력]
첫 번째 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스 별로 첫 줄에는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고,
둘째 줄에는 각 날의 매매가를 나타내는 N개의 자연수들이 공백으로 구분되어 순서대로 주어진다.
각 날의 매매가는 10,000이하이다.
[출력]
각 테스트 케이스마다 ‘#x’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고, 최대 이익을 출력한다.
[예제 풀이]
1번째 케이스는 아무 것도 사지 않는 것이 최대 이익이다.
2번째 케이스는 1,2일에 각각 한 개씩 사서 세 번째 날에 두 개를 팔면 10의 이익을 얻을 수 있다.
첫 번째, 이중 FOR문으로 풀기
다만 숫자가 커지면 계산 결과 엄청 오래 걸림.
현재의 인덱스보다 뒤에 있는 아이들 중 큰 아이를 잡아서 현재의 인덱스에 있는 아이를 빼줌. 그리고 ans 에다가 차곡 차곡 더한다.
for tc in range(1, int(input()) +1):
N = int(input())
cost = list(map(int, input().split()))
ans = 0
# 만약 숫자가 5까지 있다면 i는 1부터 4까지 필요함.
# 뒤에 비교할 숫자가 남아 있어야 하니까
for i in range(N-1):
# 첫 번째 숫자를 max에 넣고 뒤에 더 큰 놈이 있나 비교
max_value = cost[i]
# 첫 번째 친구 이후로 비교할 아이들
for k in range(i+1, N):
if max_value < cost[k]:
max_value = cost[k]
# 요기서 바로 ans += max-cost해버리면 안댐~~~~~
# 왜냐하면 max에 들어갔던 애들을 하나하나 다 더하니까
# if문에서 벗어나서 다시 max가 cost[i]보다 큰 지 검사하고 ans에다가 값을 더해줘야 함~~~
if max_value > cost[i]:
ans += max_value - cost[i]
print('#{} {}'.format(tc, ans))첫 번째 방법은 처음부터 하나하나 다 검사하니까 오래 걸림
그렇다면 뒤에부터 검사하귀
for tc in range(1, int(input()) +1):
N = int(input())
cost = list(map(int, input().split()))
ans = 0
# 제일 뒤부터 검사할 것이니 제일 뒤에 값을 처음에 넣어 줌.
max_value = cost[-1]
# 제일 뒤의 앞부터 제일 처음까지 검사할 것임.
for i in range(N-2, -1, -1):
# 만약 뒤에 값이 지금 검사하는 애보다 크면
if max_value > cost[i]:
# ans에다가 차액 추가
ans += max_value - cost[i]
# 아니라면 max 값을 갱신해줘라
else:
max_value = cost[i]
print('#{} {}'.format(tc, ans))낼 다시 풀어봐야징
갹