Jam's story

[백준-22871] 징검다리 건너기 -java 본문

코딩테스트/백준

[백준-22871] 징검다리 건너기 -java

애플쩀 2022. 8. 12. 09:39

 

 

 

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));
  }
}

 

 

 

 


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

 

Comments