SWEA_1859) 백만 장자 프로젝트
SWEA
# D2
1859) 백만 장자 프로젝트 (19.10.04)
문제 링크 (SW Expert Academy)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
|
import java.io.*;
import java.util.*;
public class Solution {
public static long sam = 0;
public static long ans = 0;
public static void cal(int[] arr, int s, int n) {
if(s>=n) return;
long max = 0;
int cnt = 0;
for(int j=s;j<n;j++) {
if(max<arr[j]) {
max = arr[j];
cnt = j;
}
}
if(cnt>s) {
for(int j=s;j<cnt;j++) {
sam = sam+arr[j];
}
ans = ans + (arr[cnt]*(cnt-s)) - sam;
sam=0;
}
cal(arr, cnt+1, n);
}
public static void main(String args[]) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer tk;
int t = Integer.parseInt(br.readLine());
for(int i=1;i<=t;i++) {
int n = Integer.parseInt(br.readLine());
int[] arr = new int[n];
tk = new StringTokenizer(br.readLine());
for(int j=0;j<n;j++) {
arr[j] = Integer.parseInt(tk.nextToken());
}
cal(arr, 0, n);
bw.write("#" + i + " " + ans+ "\n");
ans = 0;
}
bw.flush();
bw.close();
}
}
| cs |
* D2 마지막 문제! 정답률 순으로 풀다보니까 뒤로갈수록 복잡한 문제였다.
* 이 문제 처음에는 어떻게 해야하나 하고 생각했는데,
* 여러 케이스에서 생각해보니까 해결법이 떠올랐다.
* 일정 범위를 두고 가장 큰 값을 찾는다.
* 그 전까지는 계속 사고, 큰 값에 모두 판매.
* 그리고 가장 큰 값의 뒤도 같은 방법으로 처리해줘야 하니까
* 범위를 시작점, 가장 큰 값 까지 두고 재귀를 돌렸다.
* 시작점이 전체 배열의 마지막 부분까지 오면 끝내고, 정답을 출력.
* 아래는 처음 생각했던 코드.
* 테스트 케이스 몇개는 맞았는데, 나머지 부분이 틀려서 다시 생각해보기로 했다.
* 다음 값이 이전 값보다 크면, 이전 값에 사고,
* 다음 값이 이전 값보다 작으면, 이전 값에서 팔면 되려나 하고 만든 코드.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
|
import java.io.*;
import java.util.*;
public class Solution {
public static void main(String args[]) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer tk;
int t = Integer.parseInt(br.readLine());
for(int i=1;i<=t;i++) {
int n = Integer.parseInt(br.readLine());
int[] arr = new int[n];
int max = 0;
tk = new StringTokenizer(br.readLine());
for(int j=0;j<n;j++) {
arr[j] = Integer.parseInt(tk.nextToken());
if(max<arr[j]) max = arr[j];
}
long sam = 0;
long cnt = 0;
long ans = 0;
for(int j=1;j<n;j++) {
if(arr[j-1] <arr[j]) {
sam = sam+arr[j-1];
cnt = cnt+1;
}
else if(arr[j-1]==arr[j] && arr[j-1] != max) {
sam = sam+arr[j-1];
cnt = cnt+1;
}
else if(arr[j-1]==arr[j] && arr[j-1]==max) {
ans = ans + arr[j-1]*cnt - sam;
sam = 0;
cnt = 0;
}
else if(arr[j-1]> arr[j]) {
ans = ans + arr[j-1]*cnt - sam;
sam = 0;
cnt = 0;
}
}
if(cnt>0) {
ans = ans+ arr[n-1]*cnt - sam;
}
bw.write(String.valueOf(ans)+"\n");
}
bw.flush();
bw.close();
}
}
| cs |
* 이제 D3 풀건데, 확실히 요즘 문제를 많이 풀다보니까
* 이번 문제 전까지 D2문제는 거의 다 한번에 통과시켰다.
* 방법을 생각하는 시간도 짧아졌고...
* 근데 그래도 D2니까 ㅠㅠㅠ 이제 D3은 힘들겠징...?
* 그래도 문제 많이 풀고 잘하도록 하기!
댓글
댓글 쓰기