백준: Silver3② - 1072, 1124, 1141, 1166, 1198
</br>
실버 3 문제들 이어서 계속~
</br>
1072: 게임
https://www.acmicpc.net/problem/1072
게임 승률 1프로 올리기
int z = (100*y) / x;
if( z >= 99 ){
cout << -1 << endl;
return 0;
}
int ans = 0;
int l = 0, h = 1000000000;
while( l <= h ){
int mid = (l + h) / 2;
if( 100*(y + mid) / (x + mid) <= z ){
ans = mid+1;
l = mid+1;
}
else{
h = mid-1;
}
}
cout << ans << endl;
100*(y + k) / (x + k)로 승률을 구할 수 있다.
하나 씩 찾으면 당연히 시간 초과 나므로 이분탐색을 사용한다.
참고로 여기서 범위가 1 ≤ X ≤ 1,000,000,000 이므로 x, y를 long long을 사용해 줘야 함…
</br>
1124: 언더프라임
https://www.acmicpc.net/problem/1124
수를 소인수분해해서 나온 소수들의 개수가 소수인 수가 언더프라임
isPrime[0] = -1;
isPrime[1] = -1;
for(int i = 2; i < b+1; i++){
if( isPrime[i] != -1 ){
primes.push_back(i);
isPrime[i] = 1;
for(int j = 2; i*j < b+1; j++){
isPrime[i*j] = -1;
}
}
}
일단 소수 나오면 바로 이렇게 에라토스테네스의 체로 dp 구하기.
이번엔 일단 풀어 봤는데 시간이 꽤 걸리길래 다른 방식으로도 풀어 봤다.
방법 1
int ans = 0;
for(int i = a; i < b+1; i++){
int k = i, cnt = 0;
for(int j = 0; primes[j] <= k && j < primes.size(); j++){
while( k % primes[j] == 0 ){
cnt++;
k /= primes[j];
}
}
if( isPrime[cnt] == 1 ){
ans++;
}
}
cout << ans << endl;
말 그대로 수가 있으면 소수로 쪼개면서 카운트하고, 그 카운트를 다시 소수인 지 확인해 주었다.
ex) 12 = 2 * 2 * 3
방법 2
int func(int k){
if( isPrime[k] == 1 ){
return 1;
}
else if( k%2 == 0 ){
return func(k/2) + 1;
}
else{
for(int j = 0; primes[j] <= k && j < primes.size(); j++){
if( k % primes[j] == 0 ){
return func(k/primes[j]) + 1;
}
}
}
}
// in main()
int ans = 0;
for(int i = a; i < b+1; i++){
int k = i, cnt = 0;
if( isPrime[func(k)] == 1 ) ans++;
}
cout << ans << endl;
하지만 잘 생각해 보면
- 수가 소수인 경우 무조건 카운트는 하나
- 짝수인 경우 카운트는 n/2에 더하기 1
- 홀수인 경우도 어떤 k에 의해 나누어지므로 n/k에 더하기 1
이므로 해당 함수를 짜서 돌려 보니 시간이 훨씬 단축 되었다.
방법 1은 308ms, 2는 8ms가 나왔다.
</br>
1141: 접두사
https://www.acmicpc.net/problem/1141
단어들 집합을 받고, 접두사가 없는 가장 큰 부분 집합 크기 구하기
sort(v.begin(), v.end());
for(int i = 1; i < v.size(); i++){
bool b = true;
for(int j = 0; j < v[i-1].size(); j++){
if( v[i-1][j] != v[i][j] ){
b = false;
}
}
if( b ){
v.erase(v.begin() + i-1);
i--;
}
}
cout << v.size() << endl;
입력 받아서 정렬해 주면 짧고 간단한 것일 수록 앞에 간다.
따라서 앞의 녀석과 비교해서 걔가 내 접두사가 되면 걔를 없애 버리면 됨.
남은 것들이 최대의 부분 집합이다. 싶어서 해 봤는데 잘 된다.
ex) run, runi, runrun과 같을 경우 run이 runi의 접두사니까 없애 버리면 됨
정렬하면 run, riii, runrun 같은 일은 없으니까 되는 게 맞다
</br>
1166: 선물
https://www.acmicpc.net/problem/1166
하나의 직육면체에 정육면체를 n개 넣는데, 그 정육면체 한 변의 길이의 최대 구하기
double a = 0.0, low = 0.0, high = min({l, w, h});
for(int i = 0; i < 10000; i++){
long double mid = (low+high) / 2.0;
if( ((long long)(l/mid))*((long long)(w/mid))*((long long)(h/mid)) < n ){
high = mid;
}
else{
low = mid;
}
}
cout << low << endl;
얘도 이분탐색이다. 알고리즘은 바로 생각나고 어려울 게 없는데, 자료형 때문에 애 좀 먹었다…
</br>
1198: 삼각형으로 자르기
https://www.acmicpc.net/problem/1198
문제가 말이 많은데 그냥 점 3개 골라서 삼각형 넓이가 가장 큰 거 구하기.
그림 좀만 그려 보면 바로 앎
for(int i = 0; i < n-2; i++){
for(int j = i+1; j < n-1; j++){
for(int k = j+1; k < n; k++){
ans = max( ans, abs(x[j]*y[i] + x[k]*y[j] + x[i]*y[k] - x[i]*y[j] - x[j]*y[k] - x[k]*y[i]) );
}
}
}
cout << (double)ans / 2.0 << endl;
간단하게, 조합으로 3개를 골라서 signed area로 넓이를 구한다.(2배 된 상태)
그리고 출력할 때 2로 나눠서 보내면 됨.
무슨 오차를 10^-9까지 허용한다는데 어차피 정수 좌표들이라 .5 단위로 나온다.
그런데… 계속 오답 처리 돼서 뭐지 했는데, 이상하게도 같은 코드인데 cout.precision(11);
을 넣고 double 타입으로 하니까 정답 처리 된다.
채점 방식이 어떻게 되는 건지는 모르겠음.
</br>
풀다 보니 또 실버 2가 되었다.
다음은 실버 2 문제들~~
</br>
댓글남기기