백준 17251번: 힘 겨루기

문제 설명

• https://www.acmicpc.net/problem/17251
• 두 그룹에서 가장 힘이 쎈 사람이 나와 경기를 치룹니다.
  이때 승리 확률을 구하면 됩니다.

접근법

• 경기의 결과는 전적으로 가장 힘이 센 사람의 영향을 받습니다.
  만약 참가자의 힘의 값이 중복되지 않는다면 가장 힘이 센 사람이 속한 팀이 반드시 승리하게 됩니다.
• 가장 힘이 센 사람이 여럿 존재할 수 있습니다. 이 경우 양 팀 모두에 힘이 가장 센 사람이 있다면 그 경기는 무조건 비기게 됩니다.
• 가장 힘이 센 사람이 여러명 존재할 때 모든 값이 중요한 건 아닙니다.
  이 중 첫번째 힘이 쎈 사람과 마지막 힘이 쎈 사람의 위치만 중요합니다.
  첫 사람 등장 이전까지는 무조건 오른쪽 팀이 이기고, 마지막 사람 등장 이후로는 무조건 왼쪽 팀이 이깁니다. 그리고 이 중간에는 반드시 비기게 됩니다.
  • 11911911
    • 오른쪽 승리: 1|1911911, 11|911911
    • 무승부: 119|11911, 1191|1911, 11911|911
    • 왼쪽 승리: 119119|11, 1191191|1
  • 11991911 (처음과 마지막이 아닌 최댓값은 아무런 영향을 주지 않습니다.)
    • 오른쪽 승리: 1|1991911, 11|991911
    • 무승부: 119|91911, 1199|1911, 11991|911
    • 왼쪽 승리: 119919|11, 1199191|1

정답

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

public class Main {
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		int[] arr = new int[N];
		int maxVal = 0;
		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
			maxVal = Math.max(maxVal, arr[i]);
		}
		int leftMaxValIdx = Integer.MAX_VALUE;
		int rightMaxValIdx = Integer.MIN_VALUE;
		for (int i = 0; i < N; i++) {
			if(maxVal == arr[i]) {
				leftMaxValIdx = Math.min(leftMaxValIdx, i);
				rightMaxValIdx = Math.max(rightMaxValIdx,i);
			}
		}
		
		int R = N-1-rightMaxValIdx;
		int B = leftMaxValIdx;

		if(R==B) {
			System.out.println("X");
		}else if(R>B) {
			System.out.println("R");
		}else {
			System.out.println("B");
		}	
	}
}

기타

이 문제가 왜 DP랑 부분합일까