[SWEA] 1952 수영장 (D0^ / DFS) - Java

링크

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpFQaAQMDFAUq&categoryId=AV5PpFQaAQMDFAUq&categoryType=CODE&problemTitle=%EC%88%98%EC%98%81%EC%9E%A5&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 

SW Expert Academy

 

 

 

문제 해석

- 문제 해석
수영장은 1일권, 1개월권, 3개월권, 1년권이 있음
수영장을 사용할 수 있는 최소 가격 출력

- 각 테스트 케이스 입력
첫 번째 줄 : 1일권 1개월권 3개월권 1년권가격
두 번째 줄 : 12개월 동안 각 월의 이용 날짜

 

 

 

코드

package algo.swea.d_1952;

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

public class Solution {
	static int day, month, monthThree, year;
	static int[] plan;
	static int answer;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int T = Integer.parseInt(st.nextToken());

		for (int test_case = 1; test_case <= T; test_case++) {
			st = new StringTokenizer(br.readLine());

			day = Integer.parseInt(st.nextToken());
			month = Integer.parseInt(st.nextToken());
			monthThree = Integer.parseInt(st.nextToken());
			year = Integer.parseInt(st.nextToken());

			st = new StringTokenizer(br.readLine());

			plan = new int[12];
			for (int i = 0; i < plan.length; i++) {
				plan[i] = Integer.parseInt(st.nextToken());
			}

			answer = year; // 1년권 가격을 최소로 잡고 시작
			recursive(0, 0);
			System.out.println("#" + test_case + " " + answer);

		} // [E] test_case
	}

	private static void recursive(int mon, int cost) {
		// basis part
		if (mon >= 12) {
			answer = Math.min(answer, cost);
			return;
		}

		// inductive part
		recursive(mon + 1, cost + plan[mon] * day); // 1일권 가격
		recursive(mon + 1, cost + month); // 1개월권 가격
		recursive(mon + 3, cost + monthThree); // 3개월권 가격

	}
}

 

 

 

코드 해석

1년 동안 돈을 최소로 쓰는 경우를 구해야 합니다.

가장 쉽게 떠올릴 수 있는 방법은 DFS를 통한 모든 경우의 수 탐색입니다.

 

1년권 가격을 최소로 잡고 시작하였으며,

재귀를 돌면서 각각 1일권으로 한달치를 구매하는 경우, 한달권을 사는 경우, 세달권을 사는 경우를 모두 탐방합니다. 

 

이후 선택 결과 중 최소 가격을 정답으로 출력합니다.

 

 

 

발생한 문제 & 해결 방안

~~

 

 

 

 

 

 

 

해당 코드는 에디터가 코드 연습을 위해 직접 작성하였습니다.

혹시 오류가 있거나 더 좋은 코드 방향성을 아시는 분은 댓글로 남겨주시면 감사하겠습니다!

source : https://github.com/ssh5212/conding-test-practice