백준 20856 자바 - Tunnelbaneplatser (BOJ 20856 JAVA)

문제 : boj 20856

 

 

  입력받은 a1, a2, a3, a4에 대해 확실한것부터 제거해나가면서 선택해가면 된다(그리디). 이하 설명에서 cnt는 결과값으로 출력할 변수이다. 

 

1. a4값만큼 cnt에 더한다. (4명이니 그냥 바로 앉으면 된다. 다른 그룹과 같이 앉을 수 없다.)

 

2. 다음으로 a2값을 보자. a2는 a2혼자 혹은 a2+a2, a2+2*a1의 형태로 가능하다. a3와 앉을 방법이 아예 없다. 따라서 a2를 2로 나눈 몫만큼 cnt를 더하고, a2를 2로 나눈 나머지가 있다면 cnt를 하나 더 올려주면 된다.

 

이 때 a1이 2 이상이라면 a1 두 그룹과 같이 앉고, 아니면 a2 혼자 앉으면 된다. 근데 사실 어차피 a2랑 같이 앉을 수 있는건 a1 뿐이므로 a1이 음수가 되던말던 상관없이 그냥 감소시켜도 동일하다.

 

3. 다음은 a3다. a3 혼자 앉거나, a3+a1의 형태만 가능하다. 따라서 cnt를 a3만큼 증가시키고, a1을 a3만큼 감소시키면 된다. 마찬가지로 a1이 음수가 되던 말던 상관이 없다. 

 

4. 마지막으로 a1이다. 이 땐 좀 확인이 필요한데, 이미 음수라면 a2 또는 a3와 같이 앉는걸로 a1이 모두 소진되었으므로 더 살펴보지 않아도 된다. 하지만 a2, a3를 살펴본 후에도 a1이 남았다면 a1은 4명씩 같이 앉으면 된다. a1을 4로 나눈 몫을 cnt에 더하고, 나머지가 있다면 1을 더 더해주면 된다.

 

위와 과정에서 1,2,3은 뭘 먼저하던지 상관없다. 다만 a1을 살펴본 '4'는 반드시 마지막에 해야한다.

 

 

 

코드 : 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));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int[] arr = new int[5];
        for (int i = 1; i <= 4; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int cnt = arr[4];
        cnt += arr[2]/2;
        arr[2] %= 2;
        if (arr[2] == 1) {
            cnt += 1;
            arr[1]-=2;
        }
        cnt += arr[3];
        arr[1] -= arr[3];
        if (arr[1] > 0) {
            cnt+=arr[1]/4;
            cnt+=arr[1]%4==0?0:1;
        }
        System.out.println(cnt);
    }

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