문제 : 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();
}
}
'PS > BOJ' 카테고리의 다른 글
[자바] 백준 15489 - 파스칼 삼각형 (java) (2) | 2022.09.07 |
---|---|
[자바] 백준 18251 - 내 생각에 A번인 단순 dfs 문제가 이 대회에서 E번이 되어버린 건에 관하여 (Easy) (java) (0) | 2022.09.06 |
[자바, C++] 백준 2118 - 두 개의 탑 (java cpp) (2) | 2022.09.06 |
[자바] 백준 1174 - 줄어드는 수 (java) (0) | 2022.09.05 |
[자바] 백준 25418 - 정수 a를 k로 만들기 (java) (0) | 2022.09.04 |
댓글