[백준/20035] 이동하기 5 - JAVA

📌 문제

알고리즘 분류 : 그리디
난이도 : 골드5
출처 : 백준 - 이동하기 5

🦧 문제 풀이 접근

N과 M을 입력 받는다.
A 값에는 10^9이 곱해지기 때문에 A가 우선 기준이 된다.
2가지 경우를 고려한다.

A중 최대 값의 갯수가 1개인 경우
A중 최대 값의 갯수가 2개 이상인 경우

2가지 경우에 따라 B값의 합을 계산합니다.

💻 code

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine()," ");
        int AMaxNum=-1;
        int ASum = 0;
        ArrayList<Integer> maxNumIndexArrayList = new ArrayList<>();
        for(int i=0;i<N;i++) {
            int num = Integer.parseInt(st.nextToken());
            ASum += num;
            if(num>AMaxNum) {
                AMaxNum = num;
                maxNumIndexArrayList.clear();
                maxNumIndexArrayList.add(i);
            }
            else if(num==AMaxNum) {
                maxNumIndexArrayList.add(i);
            }
        }

        st = new StringTokenizer(br.readLine()," ");
        int BMaxNum=-1;
        int BSum = 0;
        int BArray[] = new int[M];
        for(int i=0;i<M;i++) {
            int num = Integer.parseInt(st.nextToken());
            BArray[i]=num;
            BSum += num;
            if(num>BMaxNum) {
                BMaxNum = num;
            }
        }
        long sum=0;
        sum += (long)(ASum + AMaxNum*(M-1))*1_000_000_000;
        if(maxNumIndexArrayList.size()==1)
            sum+=BSum + BArray[0]*(maxNumIndexArrayList.get(0)) + BArray[M-1]*(N-maxNumIndexArrayList.get(0)-1);
        else
            sum+=BSum + BArray[0]*(maxNumIndexArrayList.get(0)) + BMaxNum*(maxNumIndexArrayList.get(maxNumIndexArrayList.size()-1)-maxNumIndexArrayList.get(0)) + (N-maxNumIndexArrayList.get(maxNumIndexArrayList.size()-1)-1)*BArray[M-1];

        System.out.println(sum);
    }
}

🥇 결과

🎓 느낀점

그리디 알고리즘을 사용한지는 잘 모르겠다. 패턴을 잘 찾아서 문제를 해결했다.