SW Expert Academy
문제
...
다음과 같은 조건 하에서 사재기를 하여 최대한의 이득을 얻도록 도와주자.
1. 연속된 N일 동안의 물건의 매매가를 예측하여 알고 있다.
2. 당국의 감시망에 걸리지 않기 위해 하루에 최대 1만큼 구입할 수 있다.
3. 판매는 얼마든지 할 수 있다.
예를 들어 3일 동안의 매매가가 1, 2, 3 이라면 처음 두 날에 원료를 구매하여
마지막 날에 팔면 3의 이익을 얻을 수 있다.
**[입력]**
첫 번째 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스 별로 첫 줄에는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고,
둘째 줄에는 각 날의 매매가를 나타내는 N개의 자연수들이 공백으로 구분되어 순서대로 주어진다.
각 날의 매매가는 10,000이하이다.
**[출력]**
각 테스트 케이스마다 ‘#x’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고,
최대 이익을 출력한다.
아이디어
변수 및 자료 설정
- 연속된 N일 동안의 물건 매매가 ⇒
크기 N의 배열 ⇒ int[] pred = new int[n]
- 최대 이익 ⇒
long ⇒ long profit = 0L
- 구간 내 최고가 저장 및 업데이트 ⇒
int now = pred[n - 1] / now = pred[j]
고려 사항
- profit (반환 위한 최대 이익)길이
- 조건
2 ≤ N ≤ 1,000,000 , 매매가 최대 10,000
- 최대 이익 크기가 int 수용 범위 넘어갈 가능성 존재
- 1,000,000 * 10,000 = 10^10
- int 대신 long형 사용하여 문제 해결
문제 접근 방법
초기 접근 방식
- 배열 접근 순서
- 주어지는 매매가 배열을 앞부터 접근하고자 함
- 이후 가격을 모두 예측해야하기 때문에 구매/판매 결정에 어려움 생김
- **⇒ 뒤에서부터 접근하여 문제 풀이하여 해결**
- 반환값(이익) 계산
- 구매일 수 / 일별 구매 가격 저장 위한 배열 2개 설정
- 배열 크기 문제 / 최댓값과 비교 위해 2개의 배열(구매일, 일별 구매 가격) 접근 / 각 배열간 매칭 편의성 문제 발생
- **⇒ 최댓값-현재 가격 을 1:1로 비교하여 그 값을 바로 반환 자료에 저장하여 해결**
알고리즘 흐름
- 배열 최후단부터 접근
now와 배열 내부 값 1:1 비교 후 계산
- 더 큰 값이 나올 경우
now 업데이트
- 더 작은 값이 나올 경우 차익 계산하여
profit에 즉각 저장
전체 코드
import java.util.Scanner;
public class D2_1859_2 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
for (int i = 1; i <= t; i++) {
int n = sc.nextInt();
int[] pred = new int[n];
for (int j = 0; j < n; j++) {
pred[j] = sc.nextInt();
}
int now = pred[n - 1];
long profit = 0L;
for (int j = n - 1; j >= 0; j--) {
if (now > pred[j]) {
profit += now - pred[j];
} else if (now <= pred[j]) {
now = pred[j];
}
}
System.out.printf("#%d %d", i, profit);
System.out.println();
}
}
}
코드 설명
예측 매매가 초기화
...
int n = sc.nextInt();
int[] pred = new int[n];
for (int j = 0; j < n; j++) {
pred[j] = sc.nextInt();
}
...
최대 이익 업데이트
int now = pred[n - 1];
long profit = 0L;
for (int j = n - 1; j >= 0; j--) {
if (now > pred[j]) {
profit += now - pred[j];
} else if (now <= pred[j]) {
now = pred[j];
}
}
- 최후방부터 접근
- 현재 최고가와 배열 값 1:1 비교
- 더 큰 값이 나올 경우
now 업데이트
- 더 작은 값이 나올 경우 차익 계산하여
profit에 즉각 저장
정리
- 자료형 크기 주의
- 배열 이용 시 접근 순서 고려
- 해당 문제는 최전방부터 접근했을 때 고려 사항이 매우 많아짐
- 최후방부터 접근한다면 해당
- 계산 수식 간편성
- 해당 문제처럼 차익 계산 후 자료형에 저장이 필요한 문제가 많다.
- 이 때, 계산을 가장 간편하게 할 수 있는 것을 생각하는 연습 필요
- 실행 시간 단축화
- Scanner에 익숙해진 후 BufferedReader 배워서 활용한다면 실행시간 극단적으로 줄일 수 있다
- 주석 활용
- 코드 작성 시 주석을 적어둔다면 나중에 봤을 때 흐름 이해가 쉽겠다!
