백준: Gold5① - 1013, 1025, 1034
</br>
이제 골드 5를 풀어 보자~~
</br>
1013: Contact
https://www.acmicpc.net/problem/1013
문자열이 (100+1+ | 01)+ 이 규칙이 맞는지 확인하기 이산수학에서 오토마타할 때 배운 녀석이랑 같은 것 같다. +가 붙으면 반드시 하나 이상 있어야 함
방법 1.
bool func0(int i){
if( i == s.size() ) return true;
if( i + 1 == s.size() || s[i+1] != '1' ) return false;
if( i+2 == s.size() ) return true;
if( s[i+2] == '1' ) return func1(i+2);
else return func0(i+2);
}
bool func1(int i){
if( i == s.size() ) return true;
if( i + 3 >= s.size() ) return false;
if( s[i+1] != '0' || s[i+2] != '0' ) return false;
i += 3;
while( s[i] != '1' && i < s.size() ){
i++;
}
if( s[i+1] == '1' ) return func11(i+1);
else return func0(i+1);
}
bool func11(int i){
if( i == s.size() ) return true;
while( s[i] != '0' && i < s.size() ){
i++;
}
if( i == s.size() ) return true;
bool b = func0(i);
if( b ) return true;
else return func1(i-1);
}
1이 나올 경우 func1()로 10…01 형태가 맞는 지 확인하고, 그 뒤에 1이 더 나올 지 func11()로 또 확인한다.
func11()에서 마지막 1을 10…01의 시작의 1로 쓸지, 아니면 그냥 이전 10…01111의 끝의 1로 쓸지 나눠줬다.
</br>
방법 2.
regex_match(s, regex("(100+1+|01)+"))
그런데 더 찾아 보니 이런 함수가 이미 따로 있다고 한다.
저거 식 그대로 그냥 써주면 bool 타입을 리턴한다고 한다ㄷㄷ 대박
</br>
그런데 제출 결과 방법 2가 코드는 훨씬 짧았지만 메모리와 시간이 방법 1에 비해 조~금 더 나온다
</br>
1025: 제곱수 찾기
https://www.acmcpc.net/problem/1025
문제가 처음엔 뭔 말인가 싶은데 열 또는 행이 등차수열이 되는 것들의 조합이 제곱수인지 보는 거다
ex 1) 0 2
0 3
0 4
...
ex 2) 1 1
2 3
3 5
...
int ans = -1;
for(int i = n-1; i >= 0; i--){
for(int j = m-1; j >= 0; j--){
for(int x = -n+1; x < n; x++){
for(int y = -m+1; y < m; y++){
if( x == 0 && y == 0 ){
if( isSq(mmap[i][j]) )ans = max(ans, mmap[i][j]);
continue;
}
int a = i, b = j;
int t = 0;
while( 0 <= a && a < n && 0 <= b && b < m ){
t *= 10;
t += mmap[a][b];
if( isSq(t) ) ans = max(ans, t);
a += x;
b += y;
}
if( isSq(t) ) ans = max(ans, t);
}
}
}
}
cout << ans << endl;
모든 조합을 다 살피면서 제곱수인지 확인해 주고 가장 큰 제곱수를 저장한다.
중간에 바운드를 줄까도 생각했는데, n과 m의 크기가 9보다 작거나 같아서 빨리 돌아간다.
여기서 제곱수 확인하는 함수가 빠른 게 없을까 하고 찾아 봤는데,
bool isSq(int num){
int t;
switch (num & 0x0f) {
case 0:
case 1:
case 4:
case 9:
t = (int)sqrt(num);
return t*t == num;
default:
return false;
}
}
https://teus.me/9
0*0 = 0
1*1 = 1
2*2 = 4
3*3 = 9
4*4 = 6
5*5 = 5
6*6 = 6
7*7 = 9
8*8 = 4
9*9 = 1
각 자연수를 제곱했을 때 나올 수 있는 1의 자리수가 0, 1, 4, 5, 6, 9만이 가능하다는 것을 이용해 불필요한 sqrt() 연산을 줄일 수 있다고 한다.(끝자리가 2, 3, 7, 8이면 어차피 제곱수가 아니므로)
그런데 이걸 확장해서, 4진수, 8진수, 16진수 등일 때도 가능한 나머지 숫자의 경우만 확인해 보면 훨씬 줄어들 수 있다. 16진수에선 0, 1, 4, 9인지만 확인하면 되어서 75%가 배제된단다.
나머지 연산보다 더 간단하게 n & 0x0f로 16진수의 1의 자리수를 확인할 수 있어 더 좋다.
대단하다… 멋지다
10진수까지는 그렇구나 했는데 다른 진법은 생각도 못했네 나도 효율적인 사람이 되고 싶다
</br>
1034: 램프
https://www.acmcpc.net/problem/1034
k번, 한 열의 램프를 모두 껐다 켰다 하면 다 켜진 행은 최대 몇 개일까
방법 1.
int ans = 0;
for(int i = 0; i < n; i++){
int cnt = 0;
for(int j = 0; j < m; j++){
if( !mmap[i][j] ) cnt++;
}
if( k < cnt || (k-cnt) % 2 ) continue;
cnt = 0;
for(int j = 0; j < n; j++){
cnt++;
if( i == j ) continue;
for(int k = 0; k < m; k++){
if( mmap[i][k] != mmap[j][k] ){
cnt--;
break;
}
}
}
ans = max(ans, cnt);
}
cout << ans << endl;
고민을 좀 했는데, 역시 01 문제는 두 번하면 의미 없다는 걸 생각하면 된다
일단 현재 행의 0의 개수를 센다. 만약 0의 개수가 k보다 많다면, 그 행은 어차피 켤 수 없으니 패스한다.
만약 0의 개수보다 k가 클 때를 보자. 일단 0들을 전부 켜면 남은 (k-cnt)번을 더 껐다 켜야 한다. 그런데 이게 홀수면 이미 다 켜진 1을 하나는 0으로 바꿔야 하게 된다. 따라서 이 때도 이 행을 다 켤 수 없으니 패스해야 한다.
만약 이 행이 다 켜질 때(즉 0인 열들을 한 번 바꿔 다 1이 될 때), 다른 행들이 이 행과 똑같이 생겼다면 걔네들도 불이 켜지게 될 것이다. 그 수를 세 주면 된다.
즉 다르게 생긴 행은 의미가 없다는 뜻이다.
아~~ 그럼 이렇게도 풀 수도 있겠네
</br>
방법 2.
vector< pair<string, int> > v(mp.begin(), mp.end());
sort(v.begin(), v.end(), cmp);
int ans = 0;
for(int i = 0; i < v.size(); i++){
string s = v[i].first;
int t = v[i].second;
if( t <= ans ) break;
int cnt = 0;
for(int j = 0; j < m; j++){
if( s[j] == '0' ) cnt++;
}
if( k < cnt || (k-cnt) % 2 ) continue;
ans = max(ans, t);
}
cout << ans << endl;
일단 입력 받을 때 맵에 (램프 문자열, 나온 횟수)로 저장하고, 그걸 벡터로 바꿔준다(https://cyj893.github.io/algorithm/Algorithm10/ 우아하게ㅋㅋ).
그 다음 나온 횟수가 많은 순으로 정렬하고, 그 램프 행을 다 켤 수 있는지 확인한다.
이렇게 하면 바운드를 줄 수 있다. 만약 현재 ans보다 다음 살필 문자열의 나온 횟수가 더 적다면 살필 필요 없으므로 for문을 탈출하고 종료하면 된다.
</br>
재밌다 재밌어~~
</br>
댓글남기기