[Python] 21650번 Чемпионат по стрельбе

https://www.acmicpc.net/problem/21650

21650번: Чемпионат по стрельбе

---

22/08/24

 

이 문제 또한 실버 랜덤 디펜스를 하다가 만나게 된 문제이다.

 

어떻게 보면 언어의 장벽이 제일 크게 느껴졌던 문제였다.

 

잘못 해석하고, 실수해서 9번이나 틀렸습니다! 를 받았으니깐 말이다.

 

이 문제를 통해 얻은 점은 러시아어 문제를 풀 때는 영어로 한번 중역을 해야 자연스럽게 번역이 된다는 사실이다....

---

초기 접근 방법:

 

문제 요약이 먼저가 아니라 접근 방법을 먼저 쓰는 이유는 문제를 처음에 해석을 잘 못했기 때문이다.

 

일반적으로 이런 외국어 문제를 만났을때 내가 취하는 행동은 다음과 같다.

 

1. 영어 문제인가?

 

2. 영어 문제가 아닌가?

 

1번의 경우 번역기를 돌려도 되지만, 어느 정도 내가 영어를 해석할 줄 알기 때문에 번역기와 서로 대조해가며 더 자연스럽게 의미를 해석하려고 한다.

 

2번의 경우가 문제인데, 온전히 구글번역과 파파고에 의존할 수밖에 없다.....

 

그래서 이 문제를 평소에 자주 쓴 구글 번역기능을 활용하여 구글 번역을 돌려봤다.

 

그랬더니 다음과 같이 번역이 되었다......

---

정보 올림피아드의 학교 단계의 우승자는 그의 아버지가 참가한 전국 양궁 선수권 대회의 결과를 오래된 신문에서 집에서 발견했습니다. 불행히도 결과가 적힌 시트는 시간이 지남에 따라 심하게 ​​훼손되어 참가자의 이름을 알아낼 수 없었습니다. 각 참가자가 득점한 점수만 남게 되었고, 챔피언십 참가자들이 사격을 하는 순서대로 배열하였다.

아빠에게 물어본 후, 남학생은 아빠가 득점한 점수가 5점으로 끝이 났고, 우승자 중 한 명이 먼저 쏘고, 아빠의 바로 뒤에서 쏜 아빠의 친구가 더 적은 점수를 득점했다는 것을 알게 되었습니다. 이제 그는 아버지가 그 챔피언십에서 차지할 수 있는 가장 높은 자리가 어디인지 궁금했습니다. 

챔피언십에서 정확히 (k – 1)명의 참가자가 자신보다 엄격하게 더 많은 점수를 얻은 경우 대회 참가자가 k위를 차지했다고 가정합니다. 동시에 1 위를 차지한 챔피언십 참가자는 모두 승자로 간주되었습니다.

주어진 챔피언십 결과를 기반으로 정보학 올림피아드 학교 무대 우승자의 아버지가 챔피언십에서 가장 높은 자리를 차지할 수 있는 위치를 결정하는 프로그램을 작성해야 합니다.

 

입력 파일의 첫 번째 줄에는 전국 사격 선수권 대회 참가자 수인 정수 n이 포함됩니다(3 ≤ n ≤ 10^5 ).

입력 파일의 두 번째 줄에는 n개의 양의 정수가 포함되어 있으며 각 정수는 1000을 초과하지 않습니다. 즉, 해고된 순서대로 주어진 챔피언십 참가자의 점수입니다. 

---

읽어보면.... 전체적으로 무슨뜻인지 난해한 문장들이 많다.

 

일단 "아빠가 득점한 점수가 5점으로 끝이 났고, 우승자 중 한 명이 먼저 쏘고, 아빠의 바로 뒤에서 쏜 아빠의 친구가 더 적은 점수를 득점했다는 것을 알게 되었습니다." 이 부분이 무슨 소리인지 이해가 되지 않았다.

 

아빠가 득점한 점수가 5점밖에 안된다는건지, 여러 번 쏘는데, 마지막으로 쏜 점수가 5점이라는 건지(이 경우라면 적어도 5점은 넘겨야 된다는 뜻) 헷갈렸다.

 

그리고 그 이후도 우승자 중 한 명이 먼저 쏘고~ 이 부분도 전체적으로 문장이 어색해서 이해하기가 매우 힘들었다.

 

그리고 마지막으로 "해고된 순서대로....." 이 부분은 더욱 최악이였다...

 

결국 나는 파파고를 사용하여 번역을 하기로 했다.

 

파파고 번역은 다음과 같았다.

---

컴퓨터 과학 올림피아드의 학교 무대의 우승자는 그의 아버지가 참여한 국가 양궁 선수권 대회의 결과를 오래된 종이로 집에서 찾았습니다. 불행하게도, 그 결과가 담긴 종이 한 장으로 인해 시간이 많이 걸렸고, 참가자들의 성을 알아내는 것은 불가능했다. 각 참가자가 획득한 포인트만 남았고, 챔피언쉽 참가자가 사격하는 순서대로 배치되었습니다.

한 남학생이 아빠에게 물어보니 아빠의 점수가 5점 만점에 그치고, 챔피언쉽 우승자 중 한 명이 더 일찍 총을 쏘고, 아빠의 바로 뒤에 총을 쏘던 친구가 덜미를 잡혔다. 이제 그는 그 챔피언십에서 아버지가 가장 높은 자리를 차지할 수 있는지 궁금해했다.

대회 참가자가 자신보다 정확히 (k-1) 더 많은 점수를 받는다면 대회 참가자가 k-위를 차지했다고 가정하자. 동시에 1위를 차지한 챔피언십의 모든 참가자는 우승자로 간주되었습니다.

주어진 챔피언십 결과에 따라 컴퓨터 과학 올림피아드 학교 스테이지 우승자의 아버지가 챔피언십에서 가장 높은 순위를 차지할 수 있는 위치를 결정하는 프로그램을 작성해야 한다.

 

입력 파일의 첫 번째 줄에는 국가 사격 선수권 대회(3 = n = 105).

입력 파일의 두 번째 줄에는 n개의 양의 정수가 포함되어 있습니다. 각 정수는 1000을 초과하지 않습니다. 즉, 경기 참가자가 사격하는 순서대로 점수를 매깁니다.

---

덜미를 잡히다는 뭔 소리고, 5점 만점은 또 무슨 소리인지.... 더욱 이해가 되지 않았다..

 

결국 이상한 방향으로 삽질을 여러 번 했고 6번이나 틀렸습니다! 를 받았다.

 

---

이후 접근 방법:

 

문득 러시아어를 영어로 번역한 데이터가 더 많지 않을까 라는 생각을 하게 되었고, 중역을 하면 자연스러워지지 않을까라는 결론에 이르렀다.

 

 

실제로 해보니 더욱 자연스러웠고, 이 결과로 얻어낸 최종적인 문제의 번역은 다음과 같았다.

 

---

(영어 버전)

The winner of the school stage of the Olympiad in Informatics found at home in old papers the results of the national archery championship, in which his father participated.

Unfortunately, the sheet with the results was badly damaged by time, and it was impossible to make out the names of the participants.

Only the points scored by each participant remained, and they were arranged in the order in which the participants of the championship performed shooting.
After asking dad, the schoolboy found out that the number of points that dad scored ended in 5, one of the championship winners shot earlier, and dad's friend, who shot right after dad, scored less points.

Now he was wondering what was the highest place his dad could take in that championship.
We will assume that a participant in the competition took the kth place if exactly (k –1) participants in the championship scored strictly more points than he did.

At the same time, all participants of the championship who took first place were considered winners.
It is required to write a program that, based on the given results of the championship,

determines what the highest place in the championship could be taken by the father of the winner of the school stage of the Olympiad in Informatics.
The first line of the input file contains an integer n, the number of participants in the national shooting championship (3 ≤ n ≤ 10^5).
The second line of the input file contains n positive integers, each of which does not exceed 1000, the scores of the championship participants, given in the order in which they fired.

The output file should contain a single integer, the highest place that the student's dad could take.

If there is no participant in the championship that satisfies the conditions described above, output the number 0 to the output file.

 

(한국어 버전)

정보학 올림피아드의 학교 무대 우승자는 아버지가 참가한 전국 양궁 선수권 대회의 결과를 집에서 오래된 신문에서 발견했다. 안타깝게도, 결과가 적힌 시트는 시간에 의해 심하게 손상되었고, 참가자들의 이름을 알아내는 것은 불가능했다. 각 참가자가 득점한 점수만 남았고, 선수권 대회 참가자들이 사격 연습을 하는 순서로 배열되었다.
이 남학생은 아빠에게 물어본 결과, 아버지가 득점한 점수가 우승자 중 한 명이 앞서 쏜 5점으로 끝났고, 아빠 바로 뒤에 쏜 아빠 친구는 점수가 더 적다는 사실을 알게 됐다. 이제 그는 그의 아버지가 그 선수권 대회에서 가장 높은 자리를 차지할 수 있는 곳이 어디인지 궁금해하고 있었다.
만약 정확히 (k – 1) 명의 선수가 자신보다 더 많은 점수를 받았다면, 우리는 대회 참가자가 k위를 차지했다고 가정할 것이다. 동시에, 1위를 차지한 모든 선수권 대회 참가자들이 우승자로 간주되었다.
주어진 우승 결과에 따라 정보학 올림피아드 학교 무대 우승자의 아버지가 우승할 수 있는 가장 높은 자리를 결정하는 프로그램을 작성해야 한다.
입력 파일의 첫 줄에는 n개의 정수, 즉 전국 사격 선수권 대회 참가자 수(3 ≤ n ≤ 10^5)가 포함되어 있다.
입력 파일의 두 번째 줄에는 n개의 양의 정수가 포함되어 있으며, 각 정수는 1000개를 넘지 않는다.
출력 파일에는 학생의 아버지가 취할 수 있는 가장 높은 자리인 단일 정수가 포함되어야 합니다. 위에서 설명한 조건을 충족하는 챔피언쉽 참가자가 없을 경우 0번을 출력 파일로 출력합니다.

---

확실히 중역하니깐 더욱 자연스러워졌다.

 

특히 의미가 불분명했던 두 번째 문단이 더욱 확실해졌는데, 이 두번째 문단은 우승자가 아빠보다 먼저 쐈고, 아빠의 점수가 '5'로 끝났으며(5, 15, 25처럼), 아빠 바로 뒤에 쏘는 사람은 아빠보다 점수가 낮아야 한다는 뜻이었다.

 

 

이후 이를 토대로 함수를 작성했는데, 틀렸습니다! 를 3번이나 연속받아버렸다...

 

 

무엇이 문제인지 살펴보니 순위를 매기는 함수를 잘못 구성했었다.

 

 

예를 들어 예제 입력 1

7
10 20 15 10 30 5 1

과 같이 주어진 경우, 10점을 쏜 사람의 순위는 4위가 나와야 하는데 5위가 나오도록 함수를 짰던 것이다.

 

 

실수할 수 있는 부분이라고 생각되어 틀렸던 코드를 공개한다.

# 21650번 Чемпионат по стрельбе
# 구현, 정렬
import sys
input = sys.stdin.readline

n = int(input())
shooter = list(map(int, input().rstrip().split()))
def rank(arr):
    s = sorted(arr, reverse=True)
    ranking = {}
    before_index = 0
    for j in range(len(s)):
        if s[j] == s[before_index]:
            ranking[s[j]] = before_index+1
        else:
            before_index = j-1
            ranking[s[j]] = j+1
    return ranking
winner_score = max(shooter)
winner_index = shooter.index(winner_score)
ranking = rank(shooter)
possible_rank = []
for i in range(winner_index, n-1):
    if shooter[i] > shooter[i+1] and str(shooter[i])[-1] == '5':
        possible_rank.append(ranking[shooter[i]])
if possible_rank == []:
    print(0)
else:
    print(min(possible_rank))

 

이후 이를 고치고 맞았습니다! 를 얻어냈다.

 

---

최종적으로 맞은 코드는 다음과 같다. 더보기를 누르면 확인할 수 있다.

 

# 21650번 Чемпионат по стрельбе
# 구현, 정렬
import sys
input = sys.stdin.readline

n = int(input())
shooter = list(map(int, input().rstrip().split()))
def rank(arr):
    s = sorted(arr, reverse=True)
    ranking = {}
    ranking[s[0]] = 1
    before_rank = 1
    for j in range(1, len(s)):
        if s[j] == s[before_rank-1]:
            pass
        else:
            ranking[s[j]] = j+1
            before_rank = j+1
    return ranking
winner_score = max(shooter)
winner_index = shooter.index(winner_score)
ranking = rank(shooter)
possible_rank = []
for i in range(winner_index+1, n-1):
    if shooter[i] > shooter[i+1] and str(shooter[i])[-1] == '5':
        possible_rank.append(ranking[shooter[i]])
if possible_rank == []:
    print(0)
else:
    print(min(possible_rank))