[SWEA 1952] 수영장

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

SW Expert Academy

---

[1회차] 8월 24일 스터디 문제

이 때, 문제 접근 방법을 몰라서 (이런 문제 스타일을 처음 풀어봤다) 아마 인터넷 해설을 보고 풀었던 것 같다.

생각치도 못했던 방법이라(그 때는 dfs, bfs 적용 따위는 하지 못했음) 나를 충격에 빠뜨렸던 문제였다.

 

코드

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Solution {
    static int ans;
    static int[] price, months;
 
    public static void main(String[] args) throws Exception {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
         
        int T = Integer.parseInt(in.readLine());
        for (int i = 1; i <= T; i++) {
            StringTokenizer st = new StringTokenizer(in.readLine());
             
             price = new int[4];
             months = new int[12];
              
            for (int j = 0; j < 4; j++) {
                price[j] = Integer.parseInt(st.nextToken());
            }
             
            st = new StringTokenizer(in.readLine());
             
            for (int j = 0; j < 12; j++) {
                months[j] = Integer.parseInt(st.nextToken());
            }
             
            ans = price[3]; // 비교할 값 :한 달 이용할 때 
            dfs(0, 0);
             
            sb.append("#").append(i).append(" ").append(ans).append("\n");
        }
        System.out.println(sb);
    }
 
    private static void dfs(int m, int p) {
        if(m >= 12) {
            ans = Math.min(p, ans);
            return;
        }
         
        if(months[m] == 0) {    // 이용 안 하는 달은 그냥 넘어감 
            dfs(m + 1, p);
        }
        dfs(m + 1, p + price[0] * months[m]);   // 1일 이용시 
        dfs(m + 1, p + price[1]);       // 1달 이용시 
        dfs(m + 3, p + price[2]);       // 3달 이용시 
    }
}

 

---

[2회차] 9월 26일 보충 문제

스스로 풀었다. 다만 이 전 풀이가 매우 인상 깊었는지 똑같은 방법밖에 생각이 나지 않읍니다...

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Solution {
    static int[] price, months;
    static int result;
 
    public static void main(String args[]) throws Exception {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(in.readLine());
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
 
        for (int test_case = 1; test_case <= T ; test_case++) {
            price = new int[4];
            months = new int[12];
 
            st = new StringTokenizer(in.readLine());
            for (int i = 0; i < 4; i++) {
                price[i] = Integer.parseInt(st.nextToken());
            }
 
            st = new StringTokenizer(in.readLine());
            for (int i = 0; i < 12; i++) {
                months[i] = Integer.parseInt(st.nextToken());
            }
 
            result = price[3];
 
            findMinPrice(0, 0);
            sb.append("#" + test_case + " " + result + "\n");
        }
 
        System.out.println(sb);
    }
 
    private static void findMinPrice(int month, int cost) {
        // 달이 넘어가면 -> 종료조건
        if(month >= 12){
            result = result > cost? cost: result;
            return;
        }
 
        if(months[month] == 0) findMinPrice(month+1, cost);
        findMinPrice(month+1, cost + (months[month] * price[0]));
        findMinPrice(month+1, cost + price[1]);
        findMinPrice(month+3, cost + price[2]);
    }
}

 

이상함...이 전 코드와 별반 다를 것이 없는데 실행시간이 13ms 나 줄었다..? 이유가 무엇인가...

 

---

[3회차] 10월 27일 A형 대비 스터디 문제 

 

문제 접근 방법 (사용 자료구조, 알고리즘)

완전탐색, dfs 사용
0월부터 시작해서 하루, 한 달, 3달 이용권을 사용했을 때 모든 경우의 수를 탐색한다.
1년 이용권을 사용했을 경우가 가장 큰 비용이 드는 것으로 가정하고 이와 다른 경우의 수를 비교했다.

 

 

문제를 푼 시간 (문제 해석 + 문제 접근 + 코드 구현) : 3번째 푼 문제라 이게 맞는지 모르겠다만...

문제 분석	로직 설계	코드 구현
1분	1분	6분

이 정도면 외워서 푼 거 아님..?

 

 

메모리 & 시간

코드가 역시나 별반 다르지 않은데 메모리와 시간 둘 다 줄었다. 이게 무슨 일이지..? 달라진 것도 없는데..?

달라진 부분은 사용하지 않은 경우의 수에 관한 것인데... 이것이 차이가 난다고..? 역시 알다가도 모르겠음...

 

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Solution{
    static int prices[], months[], ans;
     
    public static void main(String[] args) throws Exception {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int T = Integer.parseInt(in.readLine());
         
        for (int test_case = 1; test_case <= T; test_case++) {
            prices = new int[4];
            months = new int[12];
             
            StringTokenizer st = new StringTokenizer(in.readLine());
            for (int i = 0; i < 4; i++) {
                prices[i] = Integer.parseInt(st.nextToken());
            }
             
            st = new StringTokenizer(in.readLine());
            for (int i = 0; i < 12; i++) {
                months[i] = Integer.parseInt(st.nextToken());
            }
             
            ans = prices[3];
            dfs(0, 0);
             
            sb.append("#").append(test_case).append(" ").append(ans).append("\n");
        }
        System.out.println(sb);
    }
 
    private static void dfs(int month, int price) {
        if(month >= 12) {
            ans = Math.min(ans, price);
            return;
        }
         
        dfs(month+1, price + months[month]*prices[0]);
        dfs(month+1, price + prices[1]);
        dfs(month+3, price + prices[2]);
         
    }
}