Koreatech Judge 1274 귀신의 집(JAVA)

https://judge.koreatech.ac.kr/problem.php?id=1274 

Judge - 귀신의 집

문제 유형: Math, dp?(풀이가 있을거라 예상)

 

 

문제 풀이

지난번 대회에서 아쉽게 풀지 못했던 문제를 다시 도전해봤다.

(대회 중간에 멘탈이 나가서 흑흑..)

https://judge.koreatech.ac.kr/contest.php?cid=1087 

Judge

먼저 모든 단체의 인원을 더한 후, 그 값을 %3을 했을 때, 0,1,2 로 나눠 계산해야한다.

먼저 나머지가 0이면 sum을 그대로 출력하면 될것이다.

나머지가 1이면, 단체 무리 중 %3을 했을 때 1인 것을 하나를 빼거나, 2인 것을 두개를 빼야한다.

나머지가 2이면, 단체 무리 중 %3을 했을 때 2인 것을 하나를 빼거나, 1인 것을 두개를 빼야한다.

 

이제 구현을 하면 처음으로 들 수 있는 생각이 O(n^2)풀이로 완전탐색을 통해 가장 작은 값을 찾는 방법이 있다.

하지만, 이 방법은 40000 * 40000으로 시간안에 통과가 되지 않을 것이다.

 

그래서 O(n) 풀이를 찾아야했고, 결과 먼저 입력을 받을 때 그 순간에 최소를 구하면 되겠다 생각했다.

for(int i = 0;i<n;i++){
            int k = Integer.parseInt(st.nextToken());
            sum += k;

            switch (k%3){
                case 0:
                    continue;
                case 1:
                    e1 = Math.min(e1, e2 + k);
                    e2 = Math.min(e2, k);
                    break;
                case 2:
                    e2 = Math.min(e2,e1 + k);
                    e1 = Math.min(e1, k);
                    break;
            }
        }

여기서 e1과 e2는 앞에서 말햇던 나머지가 1인 것 중 가장 작은 것, 나머지가 2인 것 중 가장 작은 것을 저장한다.

 

그리고 sum %3을 했을 때 1이면, e2 즉 나머지가 1인 것중 가장 작은 것을 뺀다.

2이면, e1 즉 나머지가 2인 것중 가장 작은 것을 뺀다.

 

전체 코드

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


public class Main {

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        int sum = 0;
        int e1 = Integer.MAX_VALUE - 10001;
        int e2 = Integer.MAX_VALUE - 10001;
        StringTokenizer st = new StringTokenizer(br.readLine());

        for(int i = 0;i<n;i++){
            int k = Integer.parseInt(st.nextToken());
            sum += k;

            switch (k%3){
                case 0:
                    continue;
                case 1:
                    e1 = Math.min(e1, e2 + k);
                    e2 = Math.min(e2, k);
                    break;
                case 2:
                    e2 = Math.min(e2,e1 + k);
                    e1 = Math.min(e1, k);
                    break;
            }
        }
        switch (sum % 3){
            case 0:
                System.out.println(sum);
                break;
            case 1:
                System.out.println(sum - e2);
                break;
            case 2:
                System.out.println(sum - e1);
                break;
        }
    }
}