[SWEA] Test샘플문제 - 1952번 수영장 문제 (dfs풀이)

dfs로 코드 짜면서 수월하게 풀리겠는데..?했으나

이것저것 잘못해놔서 틀린거 고치느라 시간 많이 썼다. 아오~~~~

별수있나..내가 아직 부족한 탓인것을..

 

<오답노트 - 1>

쓸데없는 for문도 쓰고 dfs종료조건도 잘못 썼었다.

저 이중for문 진짜..왜저랬는지..

한 노드에서는 3가지 선택지를 한번씩만 해보면 되니까 굳이 for문으로 저래놓지 않았어도 될일이었다

특히 depth == count로 최종값을 비교하고 dfs 빠져나가는 부분

이게 한번 dfs를 수행할때마다 depth가 1씩 증가하면 괜찮겠지만, 세달치 요금을 계산하는 과정에서는

그만큼 세달을 뛰어넘어야 하기 때문에 depth가 나중에 가서 딱 12가 되는게 아니라 12 이상이 될 수 있다

그래서 값이 12 이상이 되면 살펴보도록 조건문 부분을 나중에 바꿨다.

(depth라고 하니 헷갈려서 나중에는 start라고 함. 스타트 지점 달 이라는 뜻)

아 그리고 return;하는 지점도 위치 잘못해놨었다..minTotal값 갱신하지 않게 되더라도 돌아는 가야지..

 

1차 틀린코드

package SWTest;

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

public class SW_1952 {  //sw모의테스트 수영장 문제
    static int count;  //12달중 하루라도 수영장 가는 날 횟수
    static int minTotal;    //최소비용
    static int[] charges;
    static int[] plan; //1년간 이용계획

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        int T = Integer.parseInt(br.readLine());


        for (int t = 1; t <= T; t++) {
            st = new StringTokenizer(br.readLine());
            count = 0; minTotal = Integer.MAX_VALUE;    //정수범위 최댓값!!이거 이젠잊지마
            charges = new int[4];   //일/월/3달/연 별 요금
            for (int i = 0; i < 4; i++) {
                charges[i] = Integer.parseInt(st.nextToken());
            }
            st = new StringTokenizer(br.readLine());
            count = 0;
            plan = new int[13];
            for (int i = 1; i <= 12; i++) {
                plan[i] = Integer.parseInt(st.nextToken());
                if(plan[i] != 0) count++;
            }
            //연단위 가격과 dfs로 나온 결과랑은 따로 여기서 비교한다.
            //start는 1에서부터
            dfs(0, 1, 0);
            if (minTotal < charges[3]) {    //연 이용권 끊는것보다 싸다면
                bw.write("#" + t + " " + minTotal);
                bw.newLine();
            } else {    //아니라면 연이용권 끊는게 나음
                bw.write("#" + t + " " + charges[3]);
                bw.newLine();
            }

        }
        bw.flush();
        bw.close();
    }
    static void dfs(int depth, int start, int total) {
        if (depth == count) {
            if (total < minTotal) { //합산된 비용이 minTotal금액보다 적으면 갱신
                minTotal = total;
                return;
            }
        }

        for (int i = start; i < 13; i++) {
            if (plan[i] != 0) {     //하루라도 수영 하는 달만 계산하도록한다
                for (int j = 0; j < 3; j++) {
                    if (j == 0) {   //일단위 가격
                        total += charges[j] * plan[i];
                        dfs(depth+1, i + 1, total);
                        total -= charges[j] * plan[i];  //다시 빼줌
                    } else if (j == 1) {    //한달단위 가격
                        total += charges[j];
                        dfs(depth+1, i + 1, total);
                        total -= charges[j];
                    } else if (j == 2 && i <= 10) {    //세달단위 가격, 10월달 이후로는 세달권 불가
                        total += charges[j];
                        dfs(depth+3, i + 3, total); //세달권이니까 다음 탐색은 i에서 +3한 자리부터, depth도!!
                        total -= charges[j];
                    }
                }
            }

        }
    }
}

 

 

<오답노트 - 2>

여기선 dfs에서 total값 비교하기 위한 조건문을 start > last로 해놨었다.

(이부분 나중에 수정했지만 지금 생각해보니 이 부분 자체는 문제없다. 오히려 이렇게 하는게 dfs횟수 줄여줘서 좋은듯)

위에서 말한 문제점들이 여전히 고쳐지지 않은게 많은데

우선 가장 큰 문제는 이용하는 일이 없는 달에 요금을 적용하지 않고 넘어가도록 하는 부분도 있었어야 했는데 

그 부분이 없다..

그래고 내가 착각한 부분이

이용하는 일이 없는 달에는 세달치 이용권만 구매 가능하도록 코드를 써놨는데

굳이 그럴 필요 없었다 (그랬을때 더 이득인 경우가 있다고 잘못 생각함)

가독성도 별로인 엉망 코드..흑

 

1차 틀린코드

package SWTest;

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

public class SW_1952 {  //sw모의테스트 수영장 문제
    static int count;  //12달중 하루라도 수영장 가는 날 횟수
    static int minTotal;    //최소비용
    static int[] charges;
    static int[] plan; //1년간 이용계획
    static int last;    //마지막으로 수영장에 가는 달
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        int T = Integer.parseInt(br.readLine());


        for (int t = 1; t <= T; t++) {
            st = new StringTokenizer(br.readLine());
            count = 0; minTotal = Integer.MAX_VALUE;    //정수범위 최댓값!!이거 이젠잊지마
            charges = new int[4];   //일/월/3달/연 별 요금
            for (int i = 0; i < 4; i++) {
                charges[i] = Integer.parseInt(st.nextToken());
            }
            st = new StringTokenizer(br.readLine());
            count = 0;
            plan = new int[13];
            for (int i = 1; i <= 12; i++) {
                plan[i] = Integer.parseInt(st.nextToken());
                if(plan[i] != 0) last = i;
            }
            //연단위 가격과 dfs로 나온 결과랑은 따로 여기서 비교한다.
            //start는 1에서부터
            dfs(0, 1, 0);
            if (minTotal < charges[3]) {    //연 이용권 끊는것보다 싸다면
                bw.write("#" + t + " " + minTotal);
                bw.newLine();
            } else {    //아니라면 연이용권 끊는게 나음
                bw.write("#" + t + " " + charges[3]);
                bw.newLine();
            }

        }
        bw.flush();
        bw.close();
    }
    static void dfs(int depth, int start, int total) {
        if (start > last) {     //더 뒤에 0이 오는걸 제외하고 수영가는 달들을 다 봤다면
            if (total < minTotal) { //합산된 비용이 minTotal금액보다 적으면 갱신
                minTotal = total;
          
            }
            return;
        }

        for (int i = start; i < 13; i++) {
            for (int j = 0; j < 3; j++) {
                if (plan[i] != 0 && j == 0) {   //일단위 가격. i번째달에 이용하는일이 0일이라면 굳이 해볼필요없음
                    total += charges[j] * plan[i];
                    dfs(depth+1, i + 1, total);
                    total -= charges[j] * plan[i];  //다시 빼줌
                } else if (plan[i] != 0 && j == 1) {    //한달단위 가격. i번째달에 이용하는일이 0일이라면 굳이 해볼필요없음
                    total += charges[j];
                    dfs(depth+1, i + 1, total);
                    total -= charges[j];
                } else if (j == 2) {    //세달단위 가격, 10월달 이후로는 세달권 불가
                    total += charges[j];
                    dfs(depth+3, i + 3, total); //세달권이니까 다음 탐색은 i에서 +3한 자리부터, depth도!!
                    total -= charges[j];
                }
            }


        }
    }
}

 

문제점 찾아 수정하고 dfs부분 훨 깔끔해진 코드..

 

최종코드

package SWTest;

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

public class SW_1952 {  //sw모의테스트 수영장 문제
    static int minTotal;    //최소비용
    static int[] charges;
    static int[] plan; //1년간 이용계획
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        int T = Integer.parseInt(br.readLine());

        for (int t = 1; t <= T; t++) {
            st = new StringTokenizer(br.readLine());
            minTotal = Integer.MAX_VALUE;    //정수범위 최댓값!!이거 이젠잊지마
            charges = new int[4];   // 일/월/3달/연 별 요금
            for (int i = 0; i < 4; i++) {
                charges[i] = Integer.parseInt(st.nextToken());
            }
            st = new StringTokenizer(br.readLine());
            plan = new int[13];
            for (int i = 1; i <= 12; i++) {
                plan[i] = Integer.parseInt(st.nextToken());
            }
            //연단위 가격과 dfs로 나온 결과랑은 따로 여기서 비교한다.
            //start는 1에서부터
            dfs(1, 0);
            if (minTotal < charges[3]) {    //연 이용권 끊는것보다 싸다면
                bw.write("#" + t + " " + minTotal);
                bw.newLine();
            } else {    //아니라면 연이용권 끊는게 나음
                bw.write("#" + t + " " + charges[3]);
                bw.newLine();
            }

        }
        bw.flush();
        bw.close();
    }
    static void dfs(int start, int total) {
        if (start > 12) {     //start값이 12를 넘었다는건 12달 계획을 다 체크했다는 말이므로
            if (total < minTotal) { //합산된 비용이 minTotal 금액보다 적으면 갱신
                minTotal = total;
            }
            return;
        }

        if (plan[start] != 0) {   //해당 달에 이용하는일이 하루도 없다면 일일단위/한달단위/세달단위 굳이 계산안해도ㄱㅊ
            //일일 요금 적용
            total += charges[0] * plan[start];
            dfs(start + 1, total);
            total -= charges[0] * plan[start];  //다시 빼줌

            //한달 요금 적용
            total += charges[1];
            dfs(start + 1, total);
            total -= charges[1];

            //세달 요금 적용, 10월달 이후로는 세달권 불가능하다 생각했는데 아님!!그게 이득인 경우 있음
            total += charges[2];
            dfs(start + 3, total); //세달권이니까 다음 탐색은 i에서 +3한 자리부터
            total -= charges[2];

        } else {    //이용이 없는 날은 이용권 선택 굳이 안한다
            dfs(start + 1, total);
        }







    }
}