[자바] 백준 23814 - 아 저는 볶음밥이요 (java)

 문제 : boj23814

---

 

필요 알고리즘 개념

• 많은 조건 분기
  
  • 여러 가능성을 고려해야 한다.
• 수학
  
  • 이 문제를 풀기 위해 수식을 세울 수 있어야 한다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  우선 말로만 적어서 한번 생각해보자. 결국 군만두가 최대치가 되어야 한다는게 가장 중요한 조건이고, 그러면서도 볶음밥의 최대 수를 구해야 한다.

1. 그렇다면 군만두를 최대치로 만들 수 없다면 볶음밥을 아무리 많이 주문 가능해도 버려야 하는 값이 되는값이 된다.

2. 군만두 최대치를 찾았다면, 해당 값과 동일한 값을 낼 수 있는 여러 경우 중 볶음밥 최대치를 찾아야 한다.

 

 

  그럼 이걸 어떻게 찾을 수 있을까? 대강 생각하기로 N, M에서 군만두를 만들기 위해 부족한 양만큼 K에서 가져와 군만두 최대치를 만들어야 할 것임은 다들 생각했을 것 같다. 예를들어 아래와 같은 경우를 보자.

3
2 3 7

저대로 둔다면 K는 7이므로 볶음밥 7개가 가능하지만, 군만두를 3개밖에 못시킨다. 하지만 K에서 하나를 N에 더해주면 3, 3, 6개가 되어 군만두가 4개가 되고 이게 군만두 최대치이므로 남은 K로 볶음밥을 시키는 6이 답이 된다.

 

 

  근데 그렇다고 무조건 짜장면이나 짬뽕을 추가하면 안된다. 아래의 경우도 생각해보자.

3
2 3 9

이대로 둔다면 볶음밥9개, 군만두 4개이다. 여기서 무조건 N에 1개가 필요하다고 K에서 빼서 주면 3, 3, 8개가 된다. 이 경우 볶음밥8개, 군만두4개로 군만두 수가 동일한 최대치이다. 따라서 이 경우엔 N에 주지않고 처음 그대로 둔 9개가 최대치이다.

 

 

  그럼 이 복잡한걸 어떻게 찾아야 할까? 그냥 모든 경우의 수를 생각해보면 된다. 경우의 수는 아래와 같다. 코드에도 동일하게 A,B,C,D로 주석을 달아두었다.

[A] 짜장면이나 짬뽕을 더 시키지 않고 처음 그대로에서 볶음밥과 군만두 수를 구한다.

[B] 짜장면이 D로 나누어 떨어지지 않는다면 짜장면을 D로 나누어 떨어질만큼 K에서 빼서 추가해주고 볶음밥과 군만두 수를 구한다.

[C] 짬뽕에 대해 [B]와 동일한 로직을 진행한다.

[D] 짜장면, 짬뽕 둘 다에 대해 [B]와 동일한 로직을 진행한다.

 

 

  그리고 위의 로직을 진행하면서 현재까지 찾은 군만두 최대값과 군만두 수가 동일하다면 볶음밥의 최대치를 찾고, 만약 군만두 최대값이 더 커진다면 기존 볶음밥 최대값은 무시하고 현재 군만두 최대값에 따른 볶음밥 수로 변경해준다. 로직은 결국 수식을 세워 진행해야 한다. 어차피 C,D는 B와 동일한 방식이므로 B에 대해서만 코드에 주석으로 설명을 달아보겠다.

// [A] - 처음 그대로에서 초기 최대값 설정
long cnt = n/d + m/d + k/d;	// 군만두 최대치
long max = k;	// 볶음밥 최대치

// [B] - 짜장면에 부족한 부분을 K에서 빼서 주는 경우
// factor1을 계산해주면 현재 짜장면이 D로 나누어떨어지는 값이 되기 위해 필요한 짜장면 수가 나온다.
// 예를들어 D가 3, N이 2라면 factor1은 1이 된다.
long factor1 = (n/d+1)*d-n;
if (n%d != 0 && k-factor1 >= 0) {	// 이미 짜장면이 D로 나누어떨어진다면 진행할 필요 없다. k가 factor1을 빼서 음수가 되는건 불가능하다.
	// k-factor1은 k에서 짜장면에서 부족한 만큼을 뺀 수 이다.
    // 처음 [A]에서 군만두 최대치 구한 것과 마찬가지로 [B]에서의 군만두 최대치를 구한다.
    // 이 때 짜장면에서 부족한 수를 k에서 충당해준것이므로 n/d+1이 짜장면으로 받을 수 있는 군만두수
    // 짬뽕은 그대로 m/d 이고,
    // 볶음밥은 k에서 짜장면에 준만큼인 factor1을 뺀걸 기준으로 군만두를 얻는다.
    if (cnt == n/d+1 + m/d + (k-factor1)/d) {	// 그렇게 구한 군만두수가 최대치와 동일하다면..
        max = Math.max(max, k-factor1);	// 볶음밥 최대치만 갱신한다.
    } else if (cnt < n/d+1 + m/d + (k-factor1)/d) {	// 군만두 최대치가 갱신되었다면
        cnt = n/d+1 + m/d + (k-factor1)/d;	// 군만두 최대치를 갱신하고
        max = k-factor1;	// 기존 볶음밥 최대치는 의미없어지므로 현재 볶음밥 수로 갱신한다.
    }
}

  

 

---

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        long d = Long.parseLong(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        long n = Long.parseLong(st.nextToken());
        long m = Long.parseLong(st.nextToken());
        long k = Long.parseLong(st.nextToken());

	// [A]
        long cnt = n/d + m/d + k/d;
        long max = k;
        
        // [B]
        long factor1 = (n/d+1)*d-n;
        if (n%d != 0 && k-factor1 >= 0) {
            if (cnt == n/d+1 + m/d + (k-factor1)/d) {
                max = Math.max(max, k-factor1);
            } else if (cnt < n/d+1 + m/d + (k-factor1)/d) {
                cnt = n/d+1 + m/d + (k-factor1)/d;
                max = k-factor1;
            }
        }
		
        // [C]
        long factor2 = (m/d+1)*d-m;
        if (m%d != 0 && k-factor2 >= 0) {
            if (cnt == n/d + m/d+1 + (k-factor2)/d) {
                max = Math.max(max, k-factor2);
            } else if (cnt < n/d + m/d+1 + (k-factor2)/d) {
                cnt = n/d + m/d+1 + (k-factor2)/d;
                max = k-factor2;
            }
        }
		
        // [D]
        long factor3 = factor1 + factor2;
        if (n%d != 0 && m%d != 0 && k-factor3 >= 0) {
            if (cnt == n/d+1 + m/d+1 + (k-factor3)/d) {
                max = Math.max(max, k-factor3);
            } else if (cnt < n/d+1 + m/d+1 + (k-factor3)/d) {
                cnt = n/d+1 + m/d+1 + (k-factor3)/d;
                max = k-factor3;
            }
        }
        System.out.println(max);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}