[Baekjoon] 13382_Lab

문제(출처: https://www.acmicpc.net/problem/13382)

---

< Lab >

 

문제 풀이 

 

현재 날짜에서 3일 이전값을 확인하며 상사 방문 확률 합의 최댓값을 구한다.  

 

my solution (Java)

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 _13382_ { // Lab

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;

		int t = Integer.parseInt(bf.readLine());

		for (int i = 0; i < t; i++) {
			int n = Integer.parseInt(bf.readLine());

			double arr[] = new double[n];
			double dp[] = new double[n];
			st = new StringTokenizer(bf.readLine());
			for (int j = 0; j < n; j++) {
				arr[j] = Double.parseDouble(st.nextToken());
				dp[j] = arr[j];
			}

			double result = 0.0;

			for (int j = 0; j < n; j++) {
				for (int k = 0; k < j - 2; k++) {
					dp[j] = Math.max(dp[j], dp[k] + arr[j]);
				}
				result = Math.max(result, dp[j]);
			}

			bw.write(String.format("%.1f", result) + "\n");
		}
		bw.flush();
	}
}

변수)
t : 테스트 케이스 개수
n : 날짜 수
arr : 각 날짜의 방문 확률
dp : 각 날짜의 최대 확률 합
result : 최대 확률 합 

 

테스트 케이스 개수를 입력받는다. 테스트 케이스 개수만큼 다음 과정을 반복한다.

 

1) 날짜 수 입력

2) 날짜 수만큼 각 날짜의 방문 확률을 입력받아 arr과 dp 배열에 저장

3) 각 날짜를 탐색하며 (3일 이전 값들 + 현재 날짜의 확률을 더한 값), (현재까지 확률 합 최댓값)을 비교하여 최댓값으로 업데이트한다.

4) dp를 탐색하며 최댓값으로 result를 업데이트한다.

5) 소수 첫째 자리까지 반올림 한 값을 출력한다. 

---

---