Jam's story
[백준-22871] 징검다리 건너기 -java 본문
max값인 이유는, 그 경로를 사용하면서 그 만큼의 힘을 사용을 한 것이기 때문에
경로를 사용하면서 제일 큰 값을 구해주고
min값인 이유는, 목표치에 도달한 경로의 힘들마다 최솟값을 구해주는 것
i=3
i=4
i=5
- 우선 돌의 수를 입력받는다.
- 돌의 수만큼 그 돌에 부여된 값을 arr 배열에 입력받는다.
- sum은 그 돌까지 가는데에 필요한 힘
- N+1로 한 이유는 인덱스를 1부터 시작하기 위함
- i>j
- 첫번째 돌은 움직이지 않으니, 0
- 목표값 i-> sum[i]=에 long의 최댓값을 넣어준다.
- for-j 마지막줄에서, 최종 경로 힘중, min(최솟값)을 계산하기 때문에 , 제일 큰 값을 넣어줘도 괜찮다. j=1에서 바로 없어짐
- for-j 에서는 i가 목표값이고, j가 i를 향해 가는 것인데,
- j=3이라고 치면, 3~5까지의 합을 구해서 k에 넣고, 첫번째돌에서 3번째의 힘인 sum[3]과 max 비교
- //k는 해당 j~에서 i 까지의 힘, sum[j]는 첫번째 돌에서 j까지의 힘 그 들중 max 값을 구하고
- 최종목표값에서는 min 값을 구해준다.
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
public class Main{
private static final StringBuilder sb=new StringBuilder();
private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
public static void main(String[] args) throws IOException {
int N = Integer.parseInt(br.readLine());
StringTokenizer stk = new StringTokenizer(br.readLine());
int[] arr = new int[N + 1];
long[] sum = new long[N + 1];
for (int i = 1; i <= N; i++) {
arr[i] = Integer.parseInt(stk.nextToken());
}
sum[1] = 0;
// sum[2] = cal(1, 2, arr[1], arr[2]);
for (int i = 2; i <= N; i++) {
sum[i] = Long.MAX_VALUE;
for (int j = 1; j < i; j++) {
long k = cal(j, i, arr[i], arr[j]);
k = Math.max(k, sum[j]);
sum[i] = Math.min(sum[i], k);
}
}
sb.append(sum[N]);
System.out.println(sb.toString());
}
public static long cal(int i, int j, int s, int e) {
return (long) (j - i) * (1 + Math.abs(s - e));
}
}
중간중간 출력문을 통해, 상황을 체크하였다.
'코딩테스트 > 백준' 카테고리의 다른 글
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); (0) | 2023.07.12 |
---|---|
트리 (0) | 2023.07.12 |
[백준] DFS와 BFS - java (0) | 2022.08.10 |
[백준] 1325번 효율적인 해킹 dfs- java (0) | 2022.08.09 |
[백준] 2667번 단지번호붙이기 다시풀어보기 (DFS, BFS)- JAVA (0) | 2022.08.07 |
Comments