이성주

현재를 즐기며 미래를 만드는 개발자, 이성주입니다.

    제4회 가톨릭대학교 프로그래밍 경진대회 (CCPC) 풀이
A   [BOJ 25165] 영리한 아리의 포탈 타기
B   [BOJ 25166] 배고픈 아리의 샌드위치 구매하기
C   [BOJ 25167] 이상한 아리의 채점
F   [BOJ 25170] 명랑한 아리의 외출
H   [BOJ 25172] 꼼꼼한 쿠기의 졸업여행
I   [BOJ 25174] 힘겨운 쿠기의 식당 개업기

1. 문제

$25167$. 이상한 아리의 채점 (제4회 가톨릭대학교 프로그래밍 경진대회 (CCPC) C번)

백준 25167번 - 이상한 아리의 채점 (https://www.acmicpc.net/problem/25167)

2. 풀이

다음과 같은 NODE 구조체를 만들고, 이를 사용해서 map을 만들어 데이터를 관리하였다.

struct NODE {
    vector<string> wrong_time; // len = N, 각 문제별 처음으로 틀린 시간
    vector<string> solve_time; // len = N, 각 문제별 처음으로 맞춘 시간
}

map<string, NODE> mp; // key: 참가자 이름, value: 참가자에 대한 정보를 담은 구조체

문제를 해결하는 데 걸린 시간은 (문제를 처음 틀렸을 때의 시간)과 (문제를 해결했을 때의 시간)의 차로 구한다. 따라서, 이미 틀렸었거나 문제를 맞춘 경우는 틀린 시간의 값을 재지정하지 않는다. 또한, 이미 문제를 맞춘 경우도 맞춘 시간의 값을 재지정하지 않는다.

if ('채점 결과' == "wrong") {
  // mp['참가자 이름'].solve_time[문제 번호]와 mp['참가자 이름'].wrong_time[문제 번호]가 둘 다 초기화되지 않았다면,
  mp['참가자 이름'].wrong_time['문제 번호'] = '제출 시간';
} else if ('채점 결과' == "solve") {
  // mp['참가자 이름'].solve_time[문제 번호]가 초기화되지 않았다면,
  mp['참가자 이름'].solve_time['문제 번호'] = '제출 시간';
}

어떤 참가자 이름 name에 대해서 다음과 같은 네 가지 경우가 존재한다.

  1. wrong_time[i]와 solve_time[i]가 전부 초기화되지 않은 경우 $\rightarrow$ 제출 기록이 없는 사람은 (전체 인원수$+1$)만큼의 점수를 부여한다. $\rightarrow$ total_score[name] += (M + 1)
  2. wrong_time[i]는 초기화되지 않았는데 solve_time[i]는 초기화된 경우 $\rightarrow$ 한 번도 틀린 기록이 없이 바로 문제를 해결했다면 정답이 무효 처리되고, (전체 인원수$+1$)만큼의 점수를 부여한다. $\rightarrow$ total_score[name] += (M + 1)
  3. wrong_time[i]는 초기화 되었는데 solve_time[i]는 초기화되지 않은 경우 $\rightarrow$ 여러번 틀리고 해결하지 못한 경우에는 (전체 인원수)만큼의 점수를 부여한다. $\rightarrow$ total_score[name] += M
  4. wrong_time[i]와 solve_time[i]가 전부 초기화된 경우 $\rightarrow$ 문제별로 사람들의 순위를 매겨서 점수를 부여해야함. $\rightarrow$ {name, 제출 시간과 틀린 시간을 이용해 구한 차이값}을 v['문제 번호'] vector에 push_back 한다.

각각의 v['문제 번호'] vector에 대해서 문제를 해결하는 데 걸린 시간이 짧은 순서대로 정렬하여, 참가자들에게 점수를 부여한다(total_score에 plus).

마지막으로, pair<string, int> type의 vector를 출력 기준 조건에 맞추어 정렬한 뒤 출력하면, 정답을 얻을 수 있다.

3. 채점 결과

boj-25167

4. 회고

구현이 꽤 복잡해서 상당히 시간이 오래 걸렸던 문제였다.

5. 코드

댓글남기기