백준: Class 3 ① - 1697, 1780, 1992, 2579
</br>
클래스 3을 풀어 보자
실버 1과 골드 5가 주를 이루고 있다
</br>
1697: 숨바꼭질
https://www.acmicpc.net/problem/1697
방법 1.
if( k <= n ){
cout << n-k << endl;
return 0;
}
int nn = max(n, 1);
int cnt = 0, p = 1;
while( 1 ){
cnt++;
p *= 2;
if( nn*p > k ){
ans = min(ans, cnt + nn*p-k);
ans = min(ans, cnt-1 + k - nn*p/2);
if( n == 0 ) ans++;
break;
}
}
queue< pair<int, int> > q;
q.push(make_pair(n, 0));
while( q.size() ){
int now = q.front().first;
int d = q.front().second;
q.pop();
if( d >= ans ) continue;
if( now == k ){
ans = min(ans, d);
continue;
}
visited[now] = 1;
if( 2*now - k < ans && visited[2*now] == 0 ){
q.push(make_pair(2*now, d+1));
}
if( visited[now+1] == 0 ){
q.push(make_pair(now+1, d+1));
}
if( now-1 >= 0 && visited[now-1] == 0 ){
q.push(make_pair(now-1, d+1));
}
}
cout << ans << endl;
우와~ 어려워라
2배 앞으로 갔다가 돌아오는 경우도 있어서, 맥스를 200001로 잡고, 대략적인 ans를 구해놓고 가망성 없는 건 컷하면서 풀었던 방식이다
맨 위의 코드는 k가 n보다 작으면 뒤로 한 칸씩 돌아갈 수밖에 없으므로 bfs를 할 필요 없기 때문에 넣음
</br>
그런데 생각해 보니 k가 100000라면
40000: 50000 -> *2 10001
50000: *2 1
60000: 50000 -> *2 10001
75000: 50000 -> *2 || 100000 25001
80000: 100000 20000
90000: 100000 10000
이렇게 생각하니 2배로 넘어갔다가 돌아올 일이 없다.
아~ 결국 2배로 넘어갔다 돌아오는 건 k가 홀수일 때 k+1로 갔다가 뒤돌아가는 거 밖에 없구나
그럼 max를 200001로 잡을 필요가 없겠네
</br>
그리고 while문 안에
if( d >= ans ) continue;
if( now == k ){
ans = min(ans, d);
continue;
}
이런 조건도 의미가 없구나
bfs이기 때문에 queue에 들어간 순서대로 움직인다
즉 while문을 돈 횟수가 걸린 시간이나 다를 게 없네
그럼 continue할 것 없이 그 뒤에 것들은 다 더 오래 걸린다는 뜻
따라서 그냥 now가 k면 종료하면 된다
</br>
방법 2.
queue<int> q;
q.push(n);
visited[n] = 1;
while( q.size() ){
int now = q.front();
q.pop();
if( now == k ) break;
if( 2*now < 100001 && 2*now - k < ans && visited[2*now] == 0 ){
q.push(2*now);
visited[2*now] = visited[now]+1;
}
if( now+1 < 100001 && visited[now+1] == 0 ){
q.push(now+1);
visited[now+1] = visited[now]+1;
}
if( now-1 >= 0 && visited[now-1] == 0 ){
q.push(now-1);
visited[now-1] = visited[now]+1;
}
}
cout << visited[k]-1 << endl;
최종 코드는 이런 모양
visited[]에 그냥 저장해주는 식으로 했다
물론 시작점은 표시해야 해서 1로 하고, 나중에 답에선 1을 빼준 식으로
큐에 페어로 저장하다가 이렇게 인트 하나만 넣으니까 메모리가 절반으로 줄었다.
</br>
1780: 종이의 개수
https://www.acmicpc.net/problem/1780
bool chk(int is, int js, int d){
int k = mmap[is][js];
for(int i = is; i < is+d; i++){
for(int j = js; j < js+d; j++){
if( mmap[i][j] != k ) return false;
}
}
return true;
}
void func(int is, int js, int d){
if( chk(is, js, d) ){
if( mmap[is][js] == 0 ) zeros++;
else if( mmap[is][js] == 1 ) ones++;
else minuses++;
return;
}
int nd = d/3;
for(int i = 0; i < 3; i++){
for(int j = 0; j < 3; j++){
func(is+nd*i, js+nd*j, nd);
}
}
}
재귀로 분할 정복 하기
0 0 0 3 0 6
3 0 3 3 3 6
6 0 6 3 6 6
(6, 0) 3분할
6 0 6 1 6 2
7 0 7 1 7 2
8 0 8 1 8 2
요런 느낌
</br>
1992: 쿼드트리
https://www.acmicpc.net/problem/1992
bool chk(int is, int js, int d){
int k = mmap[is][js];
for(int i = is; i < is+d; i++){
for(int j = js; j < js+d; j++){
if( mmap[i][j] != k ) return false;
}
}
return true;
}
string func(int is, int js, int d){
if( chk(is, js, d) ){
if( mmap[is][js] == 0 ) return "0";
else return "1";
}
int nd = d/2;
string ret;
for(int i = 0; i < 2; i++){
for(int j = 0; j < 2; j++){
ret += func(is+nd*i, js+nd*j, nd);
}
}
if( ret == "0000" ) ret = "0";
else if( ret == "1111" ) ret = "1";
else{
ret.insert(0, "(");
ret.append(1, ')');
}
return ret;
}
와~~ 자료구조 수업 때 똑같은 문제 풀었었는데
그 때는 뭣도 모르고 코드 짱 더럽게 짰던 것 같은데 방금 바로 위에 1780번 풀고 보니까 엄청 간단하게 짤 수 있다
문자열을 리턴하면 된다
만약 같은 게 4개 있다면 하나로 축소한다.
그게 아니라면 괄호로 묶어 리턴하면 끝
역시 많이 풀어봐야 아는구나
</br>
2579: 계단 오르기
https://www.acmicpc.net/problem/2579
dp[n][1] = steps[n];
dp[n][0] = -3000001;
for(int i = n-1; i > 0; i--){
dp[i][0] = max(dp[i+1][1], dp[i+1][2]);
dp[i][1] = steps[i] + dp[i+1][0];
dp[i][2] = steps[i] + dp[i+1][1];
}
cout << max({dp[1][0], dp[1][1], dp[1][2]}) << endl;
시작점은 계단으로 안 치고, 마지막 계단은 꼭 밟아야 하니 마지막에서 시작하자
dp[i][안 밟음] = max(dp[i+1][밟음(1,2)])
dp[i][1번째 밟음] = 계단의 점수[i] + dp[i+1][안 밟음]
dp[i][2번째 밟음] = 계단의 점수[i] + dp[i+1][1번째 밟음]
으로 식을 세운다. 3번 연속은 밟을 수 없고, 건너 뛰는 건 한 번만 할 수 있기 때문이다.
여기서 마지막 계단은 무조건 밟아야 한다. 그래서 안 밟는 경우는 점수를 마이너스로 해서 선택될 수 없게 했다.
</br>
갑자기 골드 2가 되었다
경험치 시스템이 후하다
</br>
댓글남기기