[백준-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));
  }
}

 

 

 

 

---

중간중간 출력문을 통해, 상황을 체크하였다.