[SWEA] Test샘플문제 - 1952번 수영장 문제 (dp풀이)

dp로도 풀어봤다

사실 dp로 처음에 어케 푼다는거지..?바로 감이 오진 않았다

손으로 하나하나 풀어보면서 겨우 감을 잡고 코드를 짰다..

눈물..

나는 먼저 일일권 vs 한달권중 더 이득인걸 plan 배열에 각 달마다 넣었고

그다음 dp를 진행하며 3달권이 더 이득인지 아닌지를 판별하도록 했다

연간권이 더 이득인지는 마찬가지로 맨 마지막에 한번 비교하도록 했다

 

풀이코드

package SWTest;

import java.io.*;
import java.util.StringTokenizer;

public class SW_1952_DP {   //dp로 다시 풀이해보기

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        int T = Integer.parseInt(br.readLine());
        int[] charges;
        int[] plan;
        int[] dp;
        int temp;
        int minCharge = Integer.MAX_VALUE;
        int tempCharge;

        for (int t = 1; t <= T; t++) {
            st = new StringTokenizer(br.readLine());
            charges = new int[4];
            plan = new int[13];
            dp = new int[13];

            for (int i = 0; i < 4; i++) {
                charges[i] = Integer.parseInt(st.nextToken());
            }
            st = new StringTokenizer(br.readLine());
            for (int i = 1; i <= 12; i++) {
                plan[i] = Integer.parseInt(st.nextToken());
            }

            for (int i = 1; i <= 12; i++) {
                if (plan[i] * charges[0] < charges[1]) {    //일일권 구매하는게 한달권보다 이득이면 일일권 구매가격으로 값 새로저장
                    plan[i] = plan[i] * charges[0];
                } else {    //그 반대가 이득이면 한달권 구매가격으로 값 새로저장
                    plan[i] = charges[1];
                }
            }   //여기까지 하면 일일권vs한달권 더 이득인게 plan에 저장된상태

            for (int i = 1; i <= 12; i++) {
                //dp배열에 i 바로직전의 dp값+현재의 dp값을 더한것과 i번째달에서 두달 전까지 3달요금과 그 이전(-3번쨰달)달의 dp값을 더한것중 더 작은걸 dp에 저장
                if (i == 1) { //1월을 검사할떄는 그냥 plan에 들어있는값과 3달가를 비교한다
                    dp[i] = Integer.min(plan[i], charges[3]);
                } else if (i == 2) {    //2월을 검사할떄는 이전달 dp값+현재 plan값과 3달가를 비교한다
                    dp[i] = Integer.min(dp[i - 1] + plan[i], charges[2]);
                } else {
                    dp[i] = Integer.min((dp[i - 1] + plan[i]), dp[i - 3] + charges[2]);
                }
            }
            if (charges[3] > dp[12]) {
                bw.write("#" + t + " " + dp[12]);
            } else {
                bw.write("#" + t + " " + charges[3]);
            }
            bw.newLine();

        }
        bw.flush();
        bw.close();
    }
}