[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;
}
'자료구조, 알고리즘' 카테고리의 다른 글
| 정렬 알고리즘 종류 (0) | 2018.09.12 |
|---|---|
| 검색 알고리즘 종류 (2) | 2018.09.11 |
| 자료구조 그래프(Graph) (1) | 2018.09.06 |
| 자료구조 힙(Heap) (0) | 2018.09.05 |
| 자료구조 이진 탐색 트리(Binary Search Tree) (0) | 2018.09.01 |
| 자료구조 트리(Tree) (0) | 2018.08.30 |
| [자료구조] 큐 QUEUE (0) | 2018.08.19 |
| [자료구조] 스택 STACK (0) | 2018.08.19 |
