Swea수영장
title: 2025-08-14 author: 강병호 date: 2025-08-14 category: TIL/강병호/2025/08 layout: post (자유) —
- 1년 동안 수영장 이용권을 구매하는 최소 비용으로 완전 탐색으로 구현
- DFS를 이용해 1일, 1달, 3달을 선택하여 처리하도록 구현
- 최악의 경우 O(3^12)이므로 시간제한에 걸리지 않음.
- DFS 함수의 매개변수로 다음과 같이 처리
- month : 현재 탐색 중인 월
- cost : 누적 비용
- month가 12월을 넘으면 종료
package swea;
import java.io.*;
import java.util.StringTokenizer;
public class Q1952 {
static int d;
static int m1;
static int m3;
static int y;
static int[] plans = new int[13];
static int result;
private static void input(StringTokenizer st1, StringTokenizer st2) {
d = Integer.parseInt(st1.nextToken());
m1 = Integer.parseInt(st1.nextToken());
m3 = Integer.parseInt(st1.nextToken());
y = Integer.parseInt(st1.nextToken());
for (int i = 1; i <= 12; i++) {
plans[i] = Integer.parseInt(st2.nextToken());
}
}
private static void dfs(int month, int cost) {
if (month > 12) {
result = Math.min(result, cost);
return;
}
if (plans[month] == 0) {
dfs(month + 1, cost);
return;
}
// 1일권
dfs(month + 1, cost + d * plans[month]);
// 1달권
dfs(month + 1, cost + m1);
// 3달권
dfs(month + 3, cost + m3);
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("./Algorithm/swea/txt/Q1952.txt")));
int T = Integer.parseInt(args[0]);
for (int i = 1; i <= T; i++) {
StringTokenizer st1 = new StringTokenizer(br.readLine());
StringTokenizer st2 = new StringTokenizer(br.readLine());
input(st1, st2);
result = y;
dfs(1, 0);
System.out.println("#" + i + " " + result);
}
}
}