[SWEA] 1952번 - 수영장 풀이 및 코드 분석 (Java)

문제 링크

---

1. 문제 분석

📌 문제 개요

• 김 프로가 1년 동안 가장 적은 비용으로 수영장을 이용하는 방법을 찾아야 한다.
• 4가지 이용권 종류
  1. 1일 이용권 → 특정 일만 사용 (X일 × 1일 이용권 가격)
  2. 1달 이용권 → 해당 월 전체 이용 (1달 이용권 가격)
  3. 3달 이용권 → 연속 3개월 이용 (3달 이용권 가격)
  4. 1년 이용권 → 1년 전체 이용 (1년 이용권 가격)

🎯 요구사항

• 각 월의 이용 계획과 이용권 가격이 주어졌을 때,
  최소 비용을 계산하는 프로그램을 작성해야 한다.
• 1년 동안 최적의 조합을 찾아야 하므로
  백트래킹(Brute Force) 또는 DP(최적화 탐색)을 활용해야 한다.

---

2. 해결 방법

🔹 핵심 개념

1. 각 월마다 4가지 이용권 중 하나를 선택해야 한다.
2. 완전 탐색(백트래킹)을 이용해 모든 경우를 시도한다.
3. 이전 선택의 영향을 받으므로, 재귀를 통해 모든 경로를 탐색한다.
4. 이미 최소 비용을 찾았다면, 더 높은 비용 탐색을 하지 않는다. (백트래킹)

🔑 해결 절차

1. 입력값 처리
   • price[4] → 1일, 1달, 3달, 1년 이용권 가격
   • month[12] → 1월 ~ 12월까지 이용할 일 수
   • answer → 최소 비용을 저장
2. 백트래킹(DFS)로 최소 비용 탐색
   • 현재 m월에서 4가지 이용권을 고려하면서 백트래킹 탐색
   • 비용이 이미 answer보다 크면 더 탐색하지 않음 (Pruning)
   • m >= 12에 도달하면 최소 비용 갱신
3. 최종 출력
   • 최소 비용을 출력

---

3. 코드 구현

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

public class Solution {
    static int answer;
    static int[] price = new int[4];
    static int[] month = new int[12];

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        for (int t = 1; t <= T; t++) {
            sb.append("#").append(t).append(" ");
            answer = Integer.MAX_VALUE;

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

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

            // 백트래킹 시작
            backtracking(0, 0);

            sb.append(answer).append("\n");
        }

        System.out.println(sb);
    }

    // 백트래킹을 활용한 최소 비용 탐색
    private static void backtracking(int m, int sum) {
        if (m >= 12) {
            answer = Math.min(answer, sum);
            return;
        }

        // 1일 이용권
        backtracking(m + 1, sum + price[0] * month[m]);

        // 1달 이용권
        backtracking(m + 1, sum + price[1]);

        // 3달 이용권
        if (m + 3 <= 12) {
            backtracking(m + 3, sum + price[2]);
        }

        // 1년 이용권 (한 번만 사용)
        if (m == 0) {
            backtracking(m + 12, sum + price[3]);
        }
    }
}

---

4. 코드 분석

🔹 주요 알고리즘

1. 백트래킹을 활용한 완전 탐색
   • backtracking(m, sum)
     • m: 현재 탐색 중인 월
     • sum: 현재까지의 비용 합산
   • m >= 12이면 최솟값 갱신
2. 4가지 선택지 고려 (재귀 호출)
   • 1일 이용권 → sum + (1일 요금 × 이용일 수)
   • 1달 이용권 → sum + 1달 요금
   • 3달 이용권 → sum + 3달 요금 (3개월 후 탐색)
   • 1년 이용권 → sum + 1년 요금 (한 번만 사용 가능)

🔹 시간 복잡도 분석

• 최대 탐색 깊이 = 12 (월 단위)
• 백트래킹으로 가지치기를 하면 O(4^12) 보다 작아짐
• 최대 테스트 케이스 50개이므로,
  최대 O(50 × 4^12) → 백트래킹으로 충분히 해결 가능

---

5. 개선할 점 및 대체 방법

✅ 개선할 점

1. DP(동적 계획법)로 해결 가능
   • dp[i] = min(1일, 1달, 3달, 1년 요금)을 이용하여
     점화식을 구성하면 O(N)으로 최적화 가능
   • 하지만 백트래킹이 코드가 더 직관적이고 간결함
2. 메모이제이션 추가
   • 이미 계산된 (m, sum)을 저장하면 불필요한 연산 방지 가능

🔄 대체 방법

1. DP 활용
   • O(12) = O(1) 시간 복잡도로 더 빠르게 해결 가능

     int[] dp = new int[12];
     dp[0] = Math.min(price[0] * month[0], price[1]);
     
     for (int i = 1; i < 12; i++) {
         dp[i] = dp[i - 1] + Math.min(price[0] * month[i], price[1]);
         if (i >= 2) dp[i] = Math.min(dp[i], dp[i - 3] + price[2]);
     }
     
     int result = Math.min(dp[11], price[3]);

2. DFS + 메모이제이션 활용
   • 현재 (m, sum) 값을 Map에 저장하여 중복 탐색 방지 가능