문제 링크
- https://oj.uz/problem/view/IOI10_languages
문제 출처
- 2010 IOI Day1 4번
풀이
56점 풀이
문제에 나온 Rocchio’s Method를 그대로 구현해주면 56점이 나옵니다.
코드
98점 풀이
문장은 단어 단위로 이루어져 있다고 볼 수 있고, 단어들은 여러 문자가 연속적으로 나열되어있는 문자열입니다.
이 점을 이용해 Rocchio’s Method를 약간 수정해 이전 2~4개의 문자들을 해싱해서 함께 봐주면 대략 98점이 나옵니다.
코드
100점+ 풀이
이제 남은 2점을 위해 다른 방법을 고민해봅시다.
지금까지는 각 언어에 문자(혹은 문자열)이 등장하면 cnt배열의 값을 1로 바꿔주었습니다. 이번에는1로 바꾸는 것이 아닌, 1을 증가시키는 방법을 택해봅시다.
등장 횟수를 구할 때는 해당 언어가 등장한 횟수로 나눠주었습니다.
코드
이렇게 하면 0점에 정확도 2.5%가 나오게 됩니다.
문자(혹은 문자열)의 등장 횟수를 구할 때 해당 언어가 등장한 횟수로 나누는 것이 아닌, 언어 등장 횟수에 로그를 취한 값으로 나눠보았습니다.
코드
2.5%에서 2.7%로 증가했습니다. 그러나 여전히 0점입니다.
cnt배열의 값을 x라고 합시다. 문자(혹은 문자열)의 등장 횟수를 구할 때 x를 더하는 것이 아닌 x/(x+1)을 더해줍니다.
그리고 한 가지 아이디어를 더 추가해봤습니다.
cnt, cnt2, cnt3, cnt4의 값을 더해줄 때 각각 가중치를 줘서 더하는 방법을 선택해봤습니다.
여러 번의 시도를 통해 적절한 가중치를 찾아준다면 100점 혹은 101점을 받을 수 있습니다.
코드
전체 코드
1 |
|