[SWEA] 1952 : 수영장

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpFQaAQMDFAUq 

SW Expert Academy

처음에 코드가 너무 복잡하게 나와서 다른 방식을 생각하려는데 생각이 나지 않아 댓글을 봤더니 DP를 이용하라고 해서 DP로 풀었다. 방향이 잡혔는데도 좀 더 헤매다가 코드를 돌리는데 50개 중 48개만 맞았음..

처음엔 이용횟수가 0이면 고려하지 않았고, DP[11]과 1년권의 값을 비교해서 출력했는데 중간에 수영장을 이용하지 않는 달이 3을 넘어가면 아예 초기화가 돼버려서 올바른 답이 나오지 않는 것을 간과해서 틀렸던 것 같다.

위의 부분을 수정해서 맞았다.

오랜만에 DP문제를 풀 수 있어서 좋았음.

 

내 코드

메모리 : 20044 KB

시간 : 110 ms

코드길이 : 2085 B

 

[내 코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Solution {
	static int Day, Month, threeMonths, Year;
	static int[] DP;
	static int[] routin;

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		
		int T = Integer.parseInt(br.readLine());
		for(int t = 1; t <= T; t++) {
			sb.append('#').append(t).append(' ');
			routin = new int[12];
			DP = new int[12];

			st = new StringTokenizer(br.readLine());
			Day = Integer.parseInt(st.nextToken());
			Month = Integer.parseInt(st.nextToken());
			threeMonths = Integer.parseInt(st.nextToken());
			Year = Integer.parseInt(st.nextToken());
			
			st = new StringTokenizer(br.readLine());
			for(int i = 0; i < 12; i++) {
				routin[i] = Integer.parseInt(st.nextToken());
			}
			
			Money();
			
			sb.append(Math.min(DP[11], Year)).append('\n');
		}
		System.out.print(sb);
	}
	
	public static void Money() {
		int day = 0;
		int month = 0;
		int month_3 = 0;
		
		for(int i = 0; i < 12; i++) {
				if(i == 0) {
					day = routin[i] * Day;
					month = Month;
					month_3 = threeMonths;
					
					DP[i] = getMin(day, month, month_3);
				}
				
				else if(i == 1 || i == 2) {
					day = DP[i - 1] + routin[i] * Day;
					month = DP[i - 1] + Month * (routin[i] == 0 ? 0 : 1);
					month_3 = threeMonths;
					
					DP[i] = getMin(day, month, month_3);
				}
				
				else {
					day = DP[i - 1] + routin[i] * Day;
					month = DP[i - 1] + Month * (routin[i] == 0 ? 0 : 1);
					month_3 = DP[i - 3] + threeMonths;
					
					DP[i] = getMin(day, month, month_3);
				}
				
		}
		return;
	}
	
	public static int getMin(int num1, int num2, int num3) {
		if(num1 <= num2 && num1 <= num3) {
			return num1;
		}
		else if(num2 <= num1 && num2 <= num3) {
			return num2;
		}
		else
			return num3;
	}
	
}

 

실행시간과 코드길이가 짧은 코드가 있길래 가져옴.

메모리 : 22464 KB

시간 : 68 ms

코드길이 : 982

import java.io.*;
 
public class Solution {
    static int min;
    static int[] cost;
    static int[] plan;
    static int[] money;
 
    public static void main(String[] args) throws IOException {
        // TODO Auto-generated method stub
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine().trim());
        for(int c=1;c<=T;c++) {
            cost = new int[4];
            plan = new int[12];
            String[] s = br.readLine().trim().split(" ");
            for(int i=0;i<4;i++)
                cost[i] = Integer.parseInt(s[i]);
            s = br.readLine().trim().split(" ");
            for(int i=0;i<12;i++)
                plan[i] = Integer.parseInt(s[i]);
            money = new int[13];
            getCost();
            System.out.println("#"+c+" "+money[12]);
 
        }
    }
 
    public static void getCost() {
        for(int i=1;i<=12;i++) {
            money[i] = Math.min(money[i-1]+cost[0]*plan[i-1], money[i-1]+cost[1]);
            if(i>=3)
                money[i] = Math.min(money[i], money[i-3]+cost[2]);
        }
        if(money[12] > cost[3])
            money[12] = cost[3];
    }
}