정범의 프로그래밍 블로그 입니다.

3 분 소요

1. 핵심 개념 및 근거

핵심 개념: 동적 계획법

  • 자료구조: 1차원 배열(각 달의 이용 일수 저장, DP 테이블 저장)
  • 알고리즘 선정 근거:
    • 단계별 선택: 1월부터 12월까지 순차적으로 최선의 선택을 해야 합니다.
    • 중복 부분 문제: 4월의 최솟값을 구할 때는 1~3월까지의 최솟값이 이미 계산되어 있어야 합니다.
    • 제약사항: 이용권 종류가 4개로 고정되어 있고, 기간이 12개월로 매우 짧습니다.
  • 시간 복잡도: DP 사용 시: O(N) (여기서 N=12이므로 상수 시간에 가깝습니다.)

2. 추론 과정

  • 키워드: “가장 적은 비용”, “1일/1달/3달/1년 이용권”
  • 추론1: 특정 달(n월)의 최소 비용은 이전 달들(n-1, n-3 등)의 결과에 의존합니다.
  • 추론2: “오늘 3달권을 끊으면 미래의 3달치 비용이 결정된다”는 점에서 현재의 선택이 미래에 영향을 줍니다.
  • 추론3: 따라서 DP[i] = i월까지의 최소 비용으로 정의하여 점화식을 세울 수 있습니다.

3. 설계 및 접근

  1. 입력 저장: 12개월 이용 계획을 plan[] 배열에 저장합니다.
  2. DP 테이블 정의: dp[i]를 i월까지의 누적 최소 비용으로 설정합니다.
  3. 점화식 세우기: i월의 최소 비용은 다음 네 가지 중 최솟값입니다.
    • dp[i-1] + (plan[i] * 1일권)
    • dp[i-1] + (1달권)
    • dp[i-3] + (3달권) (단, i ≥3)
  4. 최종 비교: 계산된 dp[12]와 1년권 가격 중 더 작은 값을 출력합니다.

4. 예시 시뮬레이션

  • 이용권: 1일(10), 1달(40), 3달(100), 1년(300)
  • 계획: 1월(0일), 2월(5일), 3월(5일) …
월 (i) 계획 1일/1달 계산 3달권 고려 dp[i] (최소)
1 0일 dp[0]+0 = 0 - 0
2 5일 dp[1]+50 vs dp[1]+40 - 40 (1달권)
3 5일 dp[2]+50 vs dp[2]+40 dp[0]+100 80 (1달+1달)

5. 주의 사항

  • 3월 이전 처리: $i < 3$일 때 3달권을 쓰는 경우는 사실상 1월부터 쓰는 것과 같으므로 예외 처리가 필요합니다. (코드에서는 dp 배열 크기를 넉넉히 잡거나 조건문을 활용합니다.)
  • 1년권: 1년권은 모든 계산이 끝난 후 마지막에 한 번만 비교해도 충분합니다.

6. 코드 풀이

6.1 DP 수행

1일권과 1달권 중 유리한 것을 먼저 계산

int daypay = dp[i - 1] + (plan[i] * prices[0]);
int monthpay = dp[i - 1] + prices[1];
 
dp[i] = Math.min(daypay, monthpay);
  • 1일 이용권과 1달 이용권을 비교해서 가장 작은 비용을 찾아냅니다.

3달권 비교

if (i >= 3)
	dp[i] = Math.min(dp[i], dp[i - 3] + prices[2]);
else
	// 1~2월에 3달권을 끊는 경우 (1월부터 시작한 것으로 간주)
	dp[i] = Math.min(dp[i], prices[2]);
  • 1 ~ 2월에 3달 이용권을 끊으면 1월부터 시작한 것으로 간주합니다.

마지막 1년권과 비교

int result = Math.min(dp[12], prices[3]);
  • 마지막 1년 이용권과 dp 테이블로 계산한 값과 비교해서 최소 비용을 구합니다.

DP 수행 전체 코드

for (int i = 1; i <= 12; i++) {
	// 1. 1일권 vs 1달권 중 유리한 것으로 먼저 계산
	int daypay = dp[i - 1] + (plan[i] * prices[0]);
	int monthpay = dp[i - 1] + prices[1];
                
	dp[i] = Math.min(daypay, monthpay);
	
	// 2. 3달권 비교 (3월 이상일 때만 가능)
	if (i >= 3) 
		dp[i] = Math.min(dp[i], dp[i - 3] + prices[2]);
	else
	// 1~2월에 3달권을 끊는 경우 (1월부터 시작한 것으로 간주)
	dp[i] = Math.min(dp[i], prices[2]);
}
	
// 3. 마지막으로 1년권과 비교
int result = Math.min(dp[12], prices[3]);

6.2 전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Solution {
 
    static int[] plan = new int[13]; // 1 ~ 12월 여행 계획
    static int[] prices = new int[4]; // 이용권의 요금 모듬
    static int[] dp = new int[13]; // dp 테이블
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        // TODO Auto-generated method stub
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
 
        int T = Integer.parseInt(br.readLine());
 
        // tc
        for (int tc = 1; tc <= T; tc++) {
 
            // 이용권 요금 입력
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int i = 0; i < 4; i++) {
                prices[i] = Integer.parseInt(st.nextToken());
            }
 
            // 12개월 이용 계획 입력
            st = new StringTokenizer(br.readLine());
            for (int i = 1; i < 13; i++) {
                plan[i] = Integer.parseInt(st.nextToken());
            }
 
            // 처리
            for (int i = 1; i < 13; i++) {
 
                int daypay = dp[i - 1] + (plan[i] * prices[0]);
                int monthpay = dp[i - 1] + prices[1];
 
                dp[i] = Math.min(daypay, monthpay);
 
                if (i >= 3)
                    dp[i] = Math.min(dp[i], dp[i - 3] + prices[2]);
                else
                    dp[i] = Math.min(dp[i], prices[2]);
            }
 
            int result = Math.min(dp[12], prices[3]);
 
            // 출력 내용 추가
            sb.append("#" + tc + " " + result + "\n");
 
        } // tc 종료
 
        // 출력
        System.out.println(sb);
 
    }
 
}

카테고리:

업데이트:

참고

하나로

4 분 소요

1. 핵심 개념 및 근거