SW Expert Academy
SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!
www.swexpertacademy.com
D2문제 중 가장 맨 앞에 있지만 아껴뒀던 문제이다. 문제를 처음 봤을 때 어떻게 풀어야 될지 감이 안 왔고 정답률도 낮았기 때문이다.
먼저 처음에 완전 탐색을 해야 하나? 했지만 N 범위가 너무 커서 포기했다.
어떻게 풀어야 하나 고민하다가 다른 분들이 뒤에서부터 풀면 된다고 쓴 댓글을 보고 힌트를 얻고 풀었다ㅠㅠ
풀이
- 먼저 N 을 입력받으면 N크기의 배열 생성 후에 매매가를 저장한다.
- 뒤(N-1)부터 계산을 해준다.
- 밑의 코드에서 i 변수는 파는 날, j 변수는 사는 날이 된다.
- 앞의 날의 매매가가 현재 매매가보다 작은 동안 계속 tmp(임시 변수)에다가 현재 매매가를 더해주고 앞의 매매가는 빼준다.(파는 값은 더해주고 사는 값은 빼줌)
- j가 0보다 작아지거나(첫 날 보다 앞) 현재 매매가보다 큰 값을 발견하면 while문을 종료
- tmp를 ans(최대 이익)에 더해주고 i값을 j+1 값으로 바꿔준다.
- (파는 날짜를 바꿔준다)
- (j값이 되어야 하는데 for문에서 바로 i--가 되므로 +1을 해줌)
- 모든 날짜에 대해 계산을 해줬으면 ans 출력.
여기서 주의할 점은 ans 는 long 타입을 사용하여야 한다. 매매가는 최대 10,000이고 날짜는 최대 1,000,000이므로 최대치를 계산했을 때 int 형의 범위를 넘어갈 수 있다.
import java.io.*;
import java.util.StringTokenizer;
public class Solution {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
StringTokenizer st;
for(int tc=1; tc<=T; tc++) {
int N = Integer.parseInt(br.readLine());
int[] price = new int[N];
//매매가를 저장
st = new StringTokenizer(br.readLine());
for(int i=0; i<N; i++) {
price[i] = Integer.parseInt(st.nextToken());
}
long ans = 0; //long 타입 사용!
//맨 마지막 날짜부터 계산
//i 날짜가 파는 날, j 날짜가 사는 날이 된다.
for(int i=N-1; i>=0; i--) {
int j = i-1; //현재 파는 날짜보다 바로 앞의 날짜들을 검사
int tmp = 0;
while(j >= 0 && price[i] > price[j]) {
tmp += price[i]; //파는 날의 매매가를 더해준다.
tmp -= price[j]; //사는 날의 매매가를 빼준다.
j--; //앞의 날짜로 이동
}
ans += tmp; //이익에 더해준다.
i = j+1; //파는 날을 옮겨준다.
}
System.out.println("#"+tc+" "+ans);
}
}
}
'SWEA > D2' 카테고리의 다른 글
| [SWEA] 1288. 새로운 불면증 치료법 (0) | 2019.05.16 |
|---|---|
| [SWEA] 1928. Base64 Decoder (0) | 2019.05.16 |
| [SWEA] 1940. 가랏! RC카! (0) | 2019.05.14 |
| [SWEA] 1945. 간단한 소인수분해 (0) | 2019.05.14 |
| [SWEA] 1946. 간단한 압축 풀기 (0) | 2019.05.14 |