백준: Class 4 - 12581, 9251, 2448
</br>
클래스 4 계속
</br>
12851: 숨바꼭질 2
https://www.acmicpc.net/problem/12851
if( k == n ){
cout << 0 << endl;
cout << 1 << endl;
return 0;
}
if( k < n ){
cout << n-k << endl;
cout << 1 << endl;
return 0;
}
priority_queue< pair<int, int>, vector<pair<int, int>>, greater<> > pq;
pq.push(make_pair(0, n));
for(int i = 0; i < 100001; i++){
visited[i] = INT_MAX;
}
visited[n] = 1;
int ans = INT_MAX, cnt = 0;
while( pq.size() ){
int x = pq.top().second;
int d = pq.top().first;
pq.pop();
if( x == k ){
if( d < ans ){
ans = d;
cnt++;
}
else if( d == ans ) cnt++;
}
if( x+1 <= k && visited[x+1] > d ){
pq.push(make_pair(d+1, x+1));
visited[x+1] = d+1;
}
if( x-1 >= 0 && visited[x-1] > d ){
pq.push(make_pair(d+1, x-1));
visited[x-1] = d+1;
}
if( x != 0 && 2*x <= 100001 && visited[2*x] > d ){
pq.push(make_pair(d+1, 2*x));
visited[2*x] = d+1;
}
}
cout << ans << '\n';
cout << cnt << '\n';
끝나지 않는 숨바꼭질… 동생이 수빈이에게서 도망가고 싶은 건 아닐까
이번엔 방법의 가짓수도 출력해야 하니 브레이크 안 하고 계속 체크하면 된다
참고로 k == n나 k < n을 예외 처리해 줬었는데 얘네는 가짓수 출력을 안 해줘서 자꾸 틀렸음…
</br>
9251: LCS
https://www.acmicpc.net/problem/9251
for(int i = 1; i <= s1.size(); i++){
for(int j = 1; j <= s2.size(); j++){
if( s1[i-1] == s2[j-1] ) dp[i][j] = max(dp[i][j], dp[i-1][j-1]+1);
dp[i][j] = max({dp[i][j], dp[i-1][j], dp[i][j-1], dp[i-1][j-1]});
}
}
cout << dp[s1.size()][s2.size()] << endl;
알고리즘 시간에 교수님이 많이 했던 부분이다 요새 유전자 분석 이런 데에도 막 쓰인다고 하시고
지금 얘가 맞으면 추가하고, 아니면 패스하거나 들고 가거나 할 수 있다
dp[i][j] = max( 1. s1[i] == s2[j]라면, dp[i-1][j-1] + 1
s[i] != s[j]라면
2. dp[i-1][j] // s2[j]를 포함
3. dp[i][j-1] // s1[i]를 포함
4. dp[i-1][j-1] ) // s1[i], s2[j] 모두 포함 안 함
즉 4가지를 다 고려하면 된다.
ex) 백준 예제
ACAYKP
CAPCAK
C A P C A K
0 0 0 0 0 0 0
A 0 0 1 1 1 1 1
C 0 1 1 1 2 2 2
A 0 1 2 2 2 3 3
Y 0 1 2 2 2 3 3
K 0 1 2 2 2 3 4
P 0 1 2 3 3 3 4
</br>
2448: 별 찍기 - 11
https://www.acmicpc.net/problem/2448
#include <bits/stdc++.h>
using namespace std;
void space(int d){
for(int i = 0; i < d; i++){
cout << ' ';
}
}
void star1(){
cout << " * ";
}
void star2(){
cout << " * * ";
}
void star3(){
cout << "*****";
}
vector< vector<int> > v1, v2;
vector<int> b = {0};
int cnt;
void func2(int d){
for(int i = 0; i < v1.size(); i++){
v2.push_back(v1[i]);
}
}
void func3(int d){
int zeros = 0;
for(int i = d-1; i >= d/2; i--){
v2[i].push_back(zeros*3+1);
for(int j = 0; j < v1[i-d/2].size(); j++){
v2[i].push_back(v1[i-d/2][j]);
}
zeros += 2;
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n;
cnt = n/3;
if( n == 3 ){
star1();
cout << '\n';
star2();
cout << '\n';
star3();
cout << '\n';
return 0;
}
for(int i = 1; i < cnt; i *= 2){
if( i == 1 ){
v1.push_back(b);
v2.push_back(b);
}
func2(i);
func3(i*2);
v1 = v2;
}
for(int i = 0; i < v2.size(); i++){
space((cnt-1-i)*3);
for(int j = 0; j < v2[i].size(); j++){
if( v2[i][j] == 0 ) star1();
else space(v2[i][j]);
}
space((cnt-1-i)*3);
cout << '\n';
space((cnt-1-i)*3);
for(int j = 0; j < v2[i].size(); j++){
if( v2[i][j] == 0 ) star2();
else space(v2[i][j]);
}
space((cnt-1-i)*3);
cout << '\n';
space((cnt-1-i)*3);
for(int j = 0; j < v2[i].size(); j++){
if( v2[i][j] == 0 ) star3();
else space(v2[i][j]);
}
space((cnt-1-i)*3);
cout << '\n';
}
}
이런 극악무도한 문제가
줄 마다 별 뒤의 공백도 출력 안 하면, 출력 형식이 틀렸다고 한다
아무튼 이걸 어떻게 할 지 생각해 봤는데
0: 삼각형
0을 제외한 수: 공백의 개수
6
1 0
0 00
12
3 0
2 00
1 020
0 0000
24
7 0
6 00
5 020
4 0000
3 060
2 00400
1 0202020
0 00000000
이런 식으로, 공백이 있다고 생각 했다
따라서 차례로 삼각형 크기를 키워 나가서 v2를 목표 벡터 배열로 만들고, 출력해 줬다.
별 삼각형끼리 공백이 하나는 있어서 func3(d)에서 v2[i].push_back(zeros*3+1);라고 썼다.
</br>
*
* *
*****
* *
* * * *
***** *****
* *
* * * *
***** *****
* * * *
* * * * * * * *
***** ***** ***** *****
* *
* * * *
***** *****
* * * *
* * * * * * * *
***** ***** ***** *****
* * * *
* * * * * * * *
***** ***** ***** *****
* * * * * * * *
* * * * * * * * * * * * * * * *
***** ***** ***** ***** ***** ***** ***** *****
* *
* * * *
***** *****
* * * *
* * * * * * * *
***** ***** ***** *****
* * * *
* * * * * * * *
***** ***** ***** *****
* * * * * * * *
* * * * * * * * * * * * * * * *
***** ***** ***** ***** ***** ***** ***** *****
* * * *
* * * * * * * *
***** ***** ***** *****
* * * * * * * *
* * * * * * * * * * * * * * * *
***** ***** ***** ***** ***** ***** ***** *****
* * * * * * * *
* * * * * * * * * * * * * * * *
***** ***** ***** ***** ***** ***** ***** *****
* * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
***** ***** ***** ***** ***** ***** ***** ***** ***** ***** ***** ***** ***** ***** ***** *****
별 문제는 이쁘게 찍힌 거 볼 때는 기분이 좋다
</br>
댓글남기기