백준 14582번 오늘도 졌다 [그리디] :: 마이구미

이번 글은 백준 알고리즘 문제 "오늘도 졌다" 를 다뤄본다.

2017년 고려대학교 프로그래밍 대회에서 출제된 문제이다.

문제 풀이는 그리디 알고리즘으로 접근할 수 있다.

야구 지식이 하나도 없다면, 문제가 헷갈릴 수 있다.

그 이유로 아마 정답률이 30%대이지 않을까 생각한다.

14582번 오늘도 졌다. - https://www.acmicpc.net/problem/14582

그리디 알고리즘 - http://mygumi.tistory.com/121

프로야구팀 울림 제미니스는 오늘도 졌다. 이번에는 스타트링크 걸리버스의 4번타자가 끝내기 홈런을 쳐서 졌다. 울림 제미니스의 열렬한 팬인 지수는 속으로 화를 참으며 어떤 선수 때문에 졌는지 생각해보았다. 지수는 팀이 역전패를 했다면 불펜 투수의 책임이고, 그렇지 않다면 타자와 선발 투수의 책임이라고 생각했다.

지수는 오늘 경기에서 울림이 어떻게 졌는지 생각해보려 했지만, 기분이 너무 더러워서 뭘 할 의욕이 나지 않았다. 지수를 도와 오늘 경기에서 울림 제미니스가 역전패를 했는지 구하는 프로그램을 작성하여라. 역전패가 성립하려면 경기 도중 울림 제미니스가 이기고 있는 순간이 있어야 한다.

야구는 각 팀이 공격과 수비로 나뉘어 경기가 진행되기 때문에, 점수를 얻기 위해서는 공격할 때만 가능하다.

그렇기에 울림 제미니스팀이 먼저 공격을 진행하기 때문에, 회마다 점수를 비교할 때, 제미니스 팀을 우선으로 판단하면 된다.

0 0 2 0 0 0 0 0 0 0
1 0 2 0 0 0 0 0 0 0

위와 같이 주어졌을 경우, 울림 제미니스팀이 이기고 있던 순간이 있을까?

정답은 있다.

0 0 2 0 0 0 0 0 0 0
1 0 2 0 0 0 0 0 0 0

걸리버스팀이 1점으로 앞서고 있지만, 3회에는 먼저 제미니스팀이 공격을 하여 2점을 낸 상황이다.

그 후 걸리버스팀이 다시 2점을 내서 역전을 한 상황이다.

for(int i=1;i<10;i++) a[i] = sc.nextInt();

for(int i=1;i<10;i++) {
    aScore += a[i];

    if (aScore > bScore) {
        System.out.println("Yes");
        return;
    }

    bScore += sc.nextInt();
}
System.out.println("No");

그리디 알고리즘을 모른다면, 본인이 작성한 그리디 알고리즘 관련 글과 문제 풀이 글들을 읽어보길 바란다.

전체 소스는 아래 Github URL을 참고하길 바란다.

백준 알고리즘 문제 14582번 "오늘도 졌다" 전체 소스

https://github.com/hotehrud/acmicpc/blob/master/algorithm/Greedy/14582.java