[백준] 2839, 10162번: 설탕 배달, 전자레인지(실버4, 브론즈3, JAVA)

 

문제 링크(2839) : https://www.acmicpc.net/problem/2839

문제 링크(10162) : https://www.acmicpc.net/problem/10162

 

[백준] 2839번: 설탕 배달 (실버4, JAVA)

봉지의 최수 개수(divide)를 선언하고 사용자의 입력(N)을 받은 후 dfs 메소드를 호출합니다.

public class Main {
	int divide;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		Main main = new Main();
		
		main.dfs(N);
	}

 

문제에서 주어진 내용에서 중요한 부분은 `최대한 적은 봉지를 들고 가려고 한다.` 입니다. 최대한 적은 봉지를 들고가기 위해서는 N의 배수일 경우 먼저 계산을 하고, 그 외 (N 나누기의 몫이 0이 아닐 때)를 계산하게 되면 최대한 적은 봉지를 구할 수 있습니다.

 

아래 코드에서는 최대한 적은 봉지를 구하기 위해서는 5의 배수를 먼저 구하고, 그다음은 3의 배수, 그다음은 5로 나눠 질 때, 마지막으로 3으로 나눠질 때를 구하면 최대한 적은 봉지를 구하게 됩니다. 모두 계산을 해도 N이 0이 아니라면  정확하게 N킬로그램을 만들 수 없기 때문에 -1을 반환 합니다.

    void dfs(int N) {
        if(N%5 == 0 && N != 0) { // N이 5의 배수면 5 빼기
            divide++;
            dfs(N-5);
        } else if(N%3 == 0 && N != 0) { // N이 3의 배수면 3 빼기
            divide++;
            dfs(N-3);
        } else if(N/5 > 0 && N != 0) {
            divide++;
            dfs(N-5);
        } else if(N/3 > 0 && N != 0) {
            divide++;
            dfs(N-3);
        } else if(N == 0) {
            System.out.println(divide);
        } else {
            System.out.println(-1);
        }
    }
}

 

 

[백준] 10162번: 전자레인지(브론즈3, JAVA)

해당 문제도 위의 설탕 배달 문제와 동일한 로직으로 풀 수 있습니다. 각각 해당하는 변수들을 생성해주고 사용자의 입력을 받은 후 dfs 메소드를 호출 합니다.

import java.util.Arrays;
import java.util.Scanner;

public class Main {
	int A = 300;  // 5분
	int buttonA;
	int B = 60; // 1분
	int buttonB;
	int C = 10; // 10초
	int buttonC;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		Main main = new Main();
		main.dfs(T);
	}

 

dfs 메소드는 해당하는 값을 받아 큰 값부터 나누고, 나누어 진다면 버튼의 클릭 횟수를 증가시킨 후 재귀호출합니다. 단, 재귀호출 시 T의 값을 줄여가다가 0이 된다면 각 버튼들의 클릭 횟수를 출력하고, 0이 아니라면 -1을 출력합니다.

	void dfs(int T) {
		if(T/A != 0) {
			buttonA++;
			dfs(T-A);
		} else if(T/B != 0) {
			buttonB++;
			dfs(T-B);
		} else if(T/C != 0) {
			buttonC++;
			dfs(T-C);
		} else if(T == 0) {
			System.out.printf("%d %d %d", buttonA, buttonB, buttonC);
		} else {
			System.out.println(-1);
		}
	}
}