[BOJ] 8979 올림픽 - 문제 풀이

문제의 조건은 3가지로 단순합니다. 

1. 금메달 수가 더 많은 나라  
2. 금메달 수가 같으면, 은메달 수가 더 많은 나라 
3. 금, 은메달 수가 모두 같으면, 동메달 수가 더 많은 나라  

얼핏보면 if문을 사용하여 조건을 걸어 풀 수 있지만  

'전체 메달 수의 총합은 1,000,000 이하이다.' 라는 입력 전제조건을  활용하여 
금,은,동 메달에 각각 점수를 부여하여 각각의 메달의 최대치(1,000,000)를 획득해도 
그보다 높은 메달 1개 보다 낮은 점수를 부여하여 풀 수있는 알고리즘입니다. 

다음은 score배열에 각각의 메달에 가중치를 부여하여 계산하여 저장하는 구문입니다. 

for (int i = 0; i < country_num; i++)  { 
     score[i][0] = arr[i][0]; // 1) 
     score[i][1] = (arr[i][1] * 1000000000000) + (arr[i][2] * 1000000)+ (arr[i][3] * 1); // 2) 
} 

country_num은 입력받은 국가 개수입니다. 
score 배열은 국가 넘버, 국가 별 점수를 저장한 배열입니다. 
arr는 입력받은 배열입니다. 
1. 첫번째 열이 모두 국가 넘버이기 때문에 score배열 첫번째 행에 모두 저장합니다. 
2. arr배열의 두번째, 세번째, 네번째 열이 금,은,동메달 순이므로 각각에 가중치를 곱한 후 score배열에 저장합니다. 


두번째로 동일 점수에 대한 등수 계산법입니다. 
간단하게 구현 가능합니다. 

int count = 1; 
for (int i = 0; i < country_num; i++){ 
     if (score[i][0] == country){ 
          for (int j = 0; j < country_num; j++){ 
               if (score[i][1] < score[j][1]) count++; 
          } 
          break; 
     } 
} 
cout << count; 

두번째로 들어온 입력 (등수를 알고싶은 국가K)을 country변수에 저장한 후 
반복문을 사용하여 배열의 인덱스를 알아냅니다(각 국가가 순서대로 입력되지 않기 때문에) 
인덱스를 알아낸 상태에서 다시 반복문을 사용하여 자신의 점수보다 큰 점수를 count하면 됩니다. 
break 사용 이유는 인덱스를 이미 찾은 상태이므로 더이상 반복문을 실행하지 않아도 되기 때문입니다. 

다음 실행 코드 전체입니다. 

 * score 배열의 자료형을 unsigned long long으로 한 이유는 가중치의 총 합이 10^19이 넘어가는 숫자이기 때문에 long long을 사용해도 범위(-9x10^19~9x10^19)안에 속하지만 가중치에 음수가 없기 때문에 편의상 unsigned long long으로 표현했습니다.

*전체 소스코드 

#include <iostream> 

using namespace std; 

int main() 
{ 
     int country_num = 0; 
     int country = 0; 
     int **arr = NULL; 
     unsigned long long **score = NULL; 

     cin >> country_num >> country; 

     arr = new int*[country_num]; 
     score = new unsigned long long*[country_num]; 

     for (int i = 0; i < country_num; i++) { 
          arr[i] = new int[4]; 
          score[i] = new unsigned long long[2]; 
     } 

     for (int i = 0; i < country_num; i++) 
          for (int j = 0; j < 4; j++) 
               cin >> arr[i][j]; 

     for (int i = 0; i < country_num; i++) { 
          score[i][0] = arr[i][0]; 
          score[i][1] = (arr[i][1] * 1000000000000) + (arr[i][2] * 1000000) + (arr[i][3] * 1); 
     } 

     int count = 1; 
     for (int i = 0; i < country_num; i++) { 
          if (score[i][0] == country) { 
               for (int j = 0; j < country_num; j++) { 
                    if (score[i][1] < score[j][1]) 
                         count++; 
                    } 
               break; 
          } 
     } 
     cout << count; 

     for (int i = 0; i < country_num; i++) 
          delete[] arr[i]; 
     delete[] arr; 

     return 0; 
} 

질문사항은 댓글로 달아주세요!