[자바] 백준 24498 - blobnom (java)

 문제 : boj24498

---

 

필요 알고리즘 개념

• 그리디
  
  • 좀 생각해보면 그럴 수 밖에 없는 규칙이 보인다. 그 규칙대로 답을 구하면 된다.

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

 

---

 

풀이

  처음과 마지막이 아닌것 중 하나를 선택한다. 그럼 그 좌우는 -1, 중간은 +1이 된다. 그렇다면 각 위치가 서로 연관관계가 있을 수 있을까? 즉, 예를들어 1번째에 대해 문제에서 제시된 '행동'을 하고나서 2번째나 3번째에 대해 '행동'을 하는 경우 서로 영향을 끼칠 수 있을까? 잘 생각해보면 '가장 높은 탑의 높이'를 구하는데에는 이전에 다른 부분에 대해 '행동'하는건 손해만 있지, 더 높은 탑이 될 수는 없음을 알 수 있다.

 

  예를들어 arr[x]를 +1 시키기 위해선 arr[x-1]과 arr[x+1]은 -1이 되어야 한다. 그럼 그 이후에 arr[x-1] 또는 arr[x+1]을 +1 시키는건 그냥 제자리로 돌아오는 셈이다. 또한 arr[x+2] 혹은 arr[x-2]는 어떨까? 당연히 arr[x+1]과 arr[x-1]이 -1 되버렸으니 오히려 탑은 낮아질 것이다. arr[x+3]이상이나 arr[x-3] 이하는 영향이 아예 없다. 따라서 이 문제에서는 뭘 먼저 수행하고, 다음에 뭘 수행해야 된다는게 없고, 그냥 매번 x번째 위치의 최대값만 찾아내면 된다.

 

  1<x<N (처음과 마지막이 아닌 탑이어야함)인 x에 대해, x번째 위치의 최대값은 'arr[x] + min(arr[x-1], arr[x+1])'로 구할 수 있다. 따라서 모든 x 위치에 대해 저 값들 중 가장 큰 값이 답이 된다.

 

  주의점은, 맨 처음과 맨 끝에 있던 값이 그냥 애초에 가장 큰 값일 수 있으므로 그 부분은 별도로 처리해줘야 한다. 예를들어서 아래와 같은 경우이다.

4
100 1 5 3

위와 같은 경우, x=2인 경우 arr[2]+min(arr[1], arr[3]) = 3이다. x=3인 경우엔 6이다. 그래서 6을 출력해주면 틀리다. 왜냐면 그냥 '행동'을 아예 안하고 arr[1]을 출력해주는게 더 크기 때문이다.

 

---

 

코드 : 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));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) arr[i] = Integer.parseInt(st.nextToken());
        int answer = Math.max(arr[0], arr[n-1]);
        for (int i = 1; i < n-1; i++) answer = Math.max(answer, arr[i] + Math.min(arr[i-1], arr[i+1]));
        System.out.println(answer);
    }

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