알고리즘 문제

폐지 줍기 문제

N*N 격자로 된 땅이 있다.

 

1 0 1 7

2 0 2 0

0 2 2 1

1 3 3 2

 

오른쪽, 아래로 이동하고

오른쪽 아래 끝에서 다시 왼쪽 위로 이동한다.

이동하면서 땅에 있는 보석을 줍는다.

 

숫자는 땅에 있는 보석의 개수를 의미한다.

처음엔 먼저 N을 입력 받는다.

그리고 땅의 생김새를 입력받는다.

입력은 아래와 같다.

4

1 0 1 7

2 0 2 0

0 2 2 1

1 3 3 2

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class GarbageCollector {
	
	public static int N = 0;
	public static int map[][] = null;
	
	public static int dp[][] = null;

	public static void main(String[] args) throws Exception {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		N = Integer.parseInt(br.readLine());
		map = new int[N][N];
		dp = new int[N][N];
		StringTokenizer st = null;
		for (int i = 0 ; i < N ; i++) {
			
			st = new StringTokenizer(br.readLine());
			for (int j = 0 ; j < N ; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		int sum = 0;
		for (int i = 0 ; i < N ; i++) {
			sum = sum + map[0][i];
			dp[0][i] = sum;
		}
		sum = 0;
		for (int i = 0 ; i < N ; i++) {
			sum = sum + map[i][0];
			dp[i][0] = sum;
		}
		
		for (int i = 1 ; i < N ; i++) {
			
			for (int j = 1 ; j < N ; j++) {
				dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j]) + map[i][j];
			}
		}
		
		bw.write("" + dp[N-1][N-1]);
		bw.flush();
		bw.close();
	}
}

 

 

 

주유소 문제

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

/**
 * Fuel
 */
public class Fuel {

  public static void main(String[] args) throws Exception {
    int n;
    long[] d = new long[100000];
    long[] dist = new long[100000];
    long[] price = new long[100000];
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    n = Integer.parseInt(br.readLine());
    String distString = br.readLine();
    String[] distArr = distString.split(" ");

    String priceString = br.readLine();
    String[] priceArr = priceString.split(" ");
    for (int i = 0; i < distArr.length; i++) {
      dist[i] = Long.parseLong(distArr[i]);
    }
    for (int i = 0; i < priceArr.length; i++) {
      price[i] = Long.parseLong(priceArr[i]);
    }
    d[0] = price[0] * dist[0];
    long min = price[0];
    for (int i = 1; i < n; i++) {
      if (price[i] < min) {
        min = price[i];
      }
      d[i] = d[i -1] + min * dist[i];
    }

    bw.write("" + d[n-1]);
		bw.flush();
		bw.close();
  }
}