[백준] 17449번 순위 계산 Java

문제 링크

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

알고리즘: 그리디

문제

SNUPC(Seoul National University Painting Contest)는 서울대학교 최고의 그림 대회이다. 참가자는 순서대로 한 명씩 심사위원 앞에서 제한된 시간 동안 제시된 단어에 맞는 그림을 그리고, 심사위원이 이를 채점하는 방식으로 대회가 진행된다.

단순히 그림을 잘 그리는지를 평가하는 것이 아니라 그리는 과정에서의 퍼포먼스, 주제어를 창의적으로 해석하는 능력 등 여러 가지 기준으로 채점하기 때문에 결과로 나오는 점수도 매우 복잡하여 그대로 외우기 힘들다. 참가자였던 탐레프는 자신의 정확한 점수를 기억하는 대신 자신이 받은 중간 순위만 기억하기로 했다.

한 명의 평가가 끝나면 지금까지 점수가 매겨진 참가자 중 자신보다 점수가 높은 사람의 수 + 1이 중간 순위가 된다. 즉, 자신보다 점수가 높은 사람이 세 명이라면 4위가 되고, 점수가 더 높은 사람이 없다면 1위가 되는 식이다. 이후 다음 참가자의 점수에 따라 순위가 밀릴 수도 있다.

탐레프는 자신이 받았던 중간 순위와 이후 참가자들이 받았던 순위를 기억하고 있다. 이 정보를 바탕으로 탐레프의 최종 순위가 어떻게 될 수 있는지를 계산하는 프로그램을 작성해보자.

풀이

Tam의 순위보다 높으면 무조건 Tam의 순위는 1 내려간다.
Tam의 순위보다 낮으면 Tam의 순위는 변동 없다.
문제는 Tam의 순위와 같을 때인데 같다면 w(가중치)+1 해준다.
이후에 r+1 <= ar <= r+w 범위에 들어온다면 r을 ar로 변경해주고, w를 w-(ar-r)+1로 업데이트시켜준다.(r은 Tam rank, ar은 Tam 이후에 순위)
모든 ar 탐색을 완료했다면,
가능한 가장 높은 순위의 r을 출력, 낮은 순위의 r+w를 출력하면 된다.

소스 코드

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

class RankInfo {
    int r,w;
    boolean sc;
    RankInfo(int r, int w, boolean sc) {
        this.r = r;
        this.w = w;
        this.sc = sc;
    }
}

class Range {
    int s,e;
    Range(int s, int e) {
        this.s = s;
        this.e = e;
    }
}

public class Main {
    static int N;
    static RankInfo tam;
    static Range range;
    public static void main(String args[]) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      tam = new RankInfo(Integer.parseInt(br.readLine()), 0, false);
      N = Integer.parseInt(br.readLine());
      StringTokenizer st = new StringTokenizer(br.readLine());
      for(int i=0; i<N; i++) {
          int ar = Integer.parseInt(st.nextToken()); //after rank
          if(tam.r > ar) {
              tam = new RankInfo(tam.r+1, tam.w, tam.sc);
              range = new Range(tam.r+1, tam.r + tam.w);
          } else if(tam.r == ar) {
              tam = new RankInfo(tam.r, tam.w + 1, true);
              range = new Range(tam.r+1, tam.r + tam.w);
          } else {
              if(tam.sc) {
                  if(ar>=range.s && ar<=range.e) {
                      tam = new RankInfo(ar, tam.w - (ar - tam.r) + 1, true);
                      range = new Range(tam.r + 1, tam.r + tam.w);
                  }
              }
          }
      }
      System.out.printf("%d %d", tam.r, tam.r + tam.w);
    }
}