2022 ALOHA 월반멘토링 1주차 - C++기초, DP, 그리디, 분할정복 (후기/풀이)

이러다가는 진짜 PS접게될거 같아서 방학동안 동아리 초급반 -> 중급반 월반 과정에 신청하게 되었습니다.
월반 기준은 매주 6문제 이상 푸는거라는데 생각보다 좀 어려운거 같기도 합니다.

 

인터넷 검색까지 총동원해서 기어이 All solve는 성공하긴 했다만...

난이도나 후기는 제 개인적인 의견이고 일부 인터넷 검색을 통해 풀이를 이해한 문제들은 참고한 글들 링크를 같이 달아놓도록 하겠습니다.

 

1. 로프 

https://www.acmicpc.net/problem/2217

2217번: 로프

체감 난이도 - Easy

 

중량 w를 k개의 로프가 들때 각 로프에는 w/k의 동일한 중량이 더해지므로 로프를 연결했을때 들수 있는 최대 중량은 
(연결 되어 있는 로프들중 가장 작은 최대 중량) * (연결된 로프의 갯수) 가 됩니다.

 

각 로프가 버틸수 있는 최대 중량의 배열을 정렬해줍시다. 이 배열의 i번째 항을 w[i]라고 합시다.
이렇게 하면 i번째 로프가 연결되어 있는 로프들중 가장 작은 최대 중량을 가질때 로프들이 들수 있는 최대 중량을 w[i]*(n-i) 로 정의 할수 있습니다.

저 w[i]*(n-i) 값들중 최댓값이 문제의 답이 됩니다.

 

#include <bits/stdc++.h>
using namespace std;

long long int n;

long long int rope[100005];

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for(int i=0; i<n; i++){
        cin >> rope[i];
    }
    sort(rope, rope+n);
    long long int ans = 0;
	for(long long int i=0; i<n; i++){
		ans = max(ans, rope[i]*(n-i));
	}
	cout << ans;
}

 

2. 색종이 만들기 

https://www.acmicpc.net/problem/2630

2630번: 색종이 만들기

체감 난이도 - Medium

 

분할정복 기초 예제로 본적이 있어서 쉽게 풀었지만 처음 보면 쉽게 생각나지 않을거 같은 문제였습니다.

 

우선 풀이는 다음과 같습니다.

1 - n * n 크기의 정사각형이 1 또는 0으로만 이루어져 있는지 확인한다.
2 - 이루어져 있다면 파랑색 또는 하양색 종이 갯수를 저장하는 변수의 값을 1 증가시키고 return 한다.
3 - 이루어져 있지 않다면 n*n 크기의 정사각형을 n/2 * n/2 크기의 정사각형들로 4등분해 각각의 n/2 * n/2 정삭각형에 대하여 1~3을 반복한다. 
4 - 기저 조건은 2- 또는 확인하는 정사각형의 크기가 1인 경우입니다 (크기가 1이면 당연히 한가지 색으로만 이루어져 있기 때문)

 

1-을 확인하는 과정을 따로 함수로 빼내면 더 편합니다.

 

#include <bits/stdc++.h>
using namespace std;

int n, white, blue;
int board[130][130];

bool check(int row, int col, int size){
    int cur = board[row][col];
    for(int i=row; i<row+size; i++){
        for(int j=col; j<col+size; j++){
                if(board[i][j]!=cur){
                    return false;
                }
        }
    }
    return true;
}

void solve(int row, int col, int size){
    if(check(row,col,size)){
        if(board[row][col]==0) white++;
        else blue++;
        return;
    }
    int newsize = size/2;
    solve(row,col,newsize);
    solve(row+newsize,col,newsize);
    solve(row,col+newsize,newsize);
    solve(row+newsize,col+newsize,newsize);
}


int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cin >> board[i][j];
        }
    }
    solve(0,0,n);
    cout << white << '\n' << blue;
}

3. 2022는 무엇이 특별할까? 

https://www.acmicpc.net/problem/24268

24268번: 2022는 무엇이 특별할까?

체감 난이도 - Easy

 

앞에 0이 오면 안된다는 조건 예외처리만 신경 써주면 그렇게 어려운 문제가 아닙니다. 

우선 C++에는 next_permuation/prev_permutation이라는 굉장히 유용한 함수가 하나 있습니다. 이 함수를 사용하면 어떠한 배열이나 문자열의 다음/이전 순열을 반환해줍니다. 

 

따라서 d진법의 숫자가 모두 한번씩 등장하는 문자열을 준비해주고 (012...d)
이 문자열을 다음 순열이 없을때까지 prev_permutation을 돌려주며 이중 앞에 0이 안 붙는 것에 대해 N보다 크고 가장 작은 값을 답으로 업데이트 해주면 됩니다. 

 

미리 MX라는 충분히 큰 상수를 선언해주고 답을 MX의 값으로 초기화 시켜주면 모든 순열을 확인했을때 답이 여전히 MX라면 답이 없음을 알수 있습니다.

 

#include <bits/stdc++.h>
using namespace std;

long long int n, d;
const long long int MX = 2000000000;
long long int ans = MX;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> d;
    string s;
    for(int i=0; i<d; i++) s += (d-i+47);
	do {
        if(s[0]!='0'){
            long long int num = stoll(s, NULL, d);
            if(num < ans && num > n) ans = num;
        }
	} while (prev_permutation(s.begin(), s.end()));
    if (ans == MX) cout << -1;
    else cout << ans;
    return 0;
}

4. 에너지 모으기

https://www.acmicpc.net/problem/16198

16198번: 에너지 모으기

체감 난이도 - Medium

 

브루트포스 문제 중에서도 백트래킹 형태의 문제입니다.

먼저 각 에너지 구슬을 제거 했는지 제거하지 않았는지 상태를 저장하는 used 배열을 선언합니다.
used[i]가 1이면 제거하였다는 의미이고 0이면 아직 제거하지 않았다는 의미입니다.

 

w[i]를 i번째 에너지 구슬의 에너지라 하면 i번째 구슬을 제거하였을때 얻는 에너지는
(i번째 구슬 가장 왼쪽 근처에 있는 구슬중 제거되지 않은 구슬의 에너지) * (i번째 구슬 가장 오른쪽 근처에 있는 구슬중 제거되지 않은 구슬의 에너지)  가 됩니다.

 

그리고 우리가 i번째 구슬에 대해 할수 있는 동작은 두가지 입니다. 
1 - 제거한다
2 - 제거하지 않는다.

따라서 저 두가지 갈래에 대해 모든 경우들을 확인해주기 위해 재귀함수를 작성하면 됩니다.

#include <bits/stdc++.h>
using namespace std;

int n, ans;

int w[15];
int used[15];

void solve(int sum){
	ans = max(ans, sum);
	
	for(int i=1; i<n-1; i++){
		if(!used[i]){
			used[i]=1; // 1 - i 번째를 제거
			int left, right;
			for(int j=i-1; j>=0; j--){
				if(!used[j]){
					left = w[j];
					break;
				}
			}
			for(int j=i+1; j<n; j++){
				if(!used[j]){
					right = w[j];
					break;
				}
			}
			solve(sum+left*right); //i 번째를 제거한 갈래에 대한 호출
			used[i]=0; //i번째를 제거하지 않은 갈래를 만들기 위해
//i번째를 다시 사용하지 않은 상태로 돌려줌
		}
	}
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for(int i=0; i<n; i++){
        cin >> w[i];
    }
	solve(0);
	cout << ans;   
}

5. 부분수열의 합

https://www.acmicpc.net/problem/14225

14225번: 부분수열의 합

체감 난이도 -

Easy

 

4번과 비슷한 백트래킹 문제입니다. 다만 오히려 더 쉽습니다.

 

우선 dekiru라는 배열을 만들어 줍니다. dekiru[i]가 1이라면 i는 가능한 부분수열의 합이라는 의미입니다.

각 호출 단계에서 나온 단계합은 모두 가능한 부분수열의 합이니 각 재귀 호출 단계에서의 합에 대해 dekiru[합] 을 1로 해주고 호출이 다 종료된후 dekiru배열을 1부터 확인하며 처음으로 0이 등장하는 인덱스를 출력해주면 됩니다.

 

여기서도 기존에 주여진 수열 a에 대해 a[i]를 a의 i 번째 항이라 하면 각 a[i]에 대해 두가지 동작을 할수 있습니다.
1 - a[i]를 부분수열에 넣는다
2 - a[i]를 부분수열에 넣지 않는다

 

따라서 저 두가지 갈래를 모두 확인하는 재귀 함수를 만들면 됩니다.

 

#include <bits/stdc++.h>
using namespace std;

int n;

int arr[25];
int dekiru[2000005];

void solve(int sum, int pos){
    dekiru[sum]=1;
    if(pos==n) return; //현재 확인하는 항이 마지막 항이라면 호출 종료 더이상 넣을 항도 
// 넣지 않을 항도 없기 때문
    int newsum = sum + arr[pos];
    solve(sum, pos+1); //a[i]를 넣지 않고 다음 항으로 
    solve(newsum, pos+1); //a[i]를 넣고 다음 항으로
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for(int i=0; i<n; i++){
        cin >> arr[i];
    }
    solve(0,0);
    for(int i=1; i<=2000001; i++){
        if(!dekiru[i]){
            cout << i;
            return 0;
        }
    }
}

6. 사과나무

https://www.acmicpc.net/problem/19539

19539번: 사과나무

체감 난이도 - Hard

 

이 블로그 글을 읽는것을 추천 드립니다. 굉장히 이해하기 쉽게 자세하게 설명이 되어있습니다. 저도 이거 읽고 풀었습니다.

https://velog.io/@axiom0510/b19539

백준 사과나무(19539)

 

그래도 조금이라도 이해한 선에서 설명을 해보자면.
1 - 1, 2를 동시에 뿌리는 행위를 3을 한번 뿌리는 행위로 볼수 있기에 모든 나무들의 높이의 합이 3의 배수가 아니라면 불가능합니다.

2 - 1과 2를 동시에 같이 뿌려야 한다는 조건을 잠시 잊어보면 2를 뿌릴수 있는 최대 횟수는 나무들의 높이를 2로 나누 몫들의 합이 됩니다.

3 - 다시 1과 2를 같이 뿌려야 한다는 조건을 기억해보면 실제로 2를 뿌려야 하는 횟수는 (전체 나무높이의 합)/3 이 됩니다. (1, 2를 세트로 뿌리기 때문)

4 - 전체 나무의 높이들의 합이 3의 배수라면 우리는 2를 뿌릴수 있는 횟수에서 적당한 양을 1을 뿌리는 횟수로 바꾸어 두 횟수를 같게 만들수 있음이 보장됩니다.
5 - 따라서 나무의 높이들의 합이 3의 배수이고 2를 뿌릴수 있는 최대 횟수가 2를 뿌려야 하는 횟수보다 많다면 무조건 가능합니다. 

 

#include <bits/stdc++.h>
using namespace std;

int n;
int h[100005];

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int sum = 0;
    int twomax = 0;
    cin >> n;
    for(int i=0; i<n; i++){
        cin >> h[i];
        sum += h[i];
        twomax += h[i]/2;
    }
    if(sum%3==0 && twomax >= sum/3){
        cout << "YES";
    }
    else cout << "NO";
}

솔직히 왜 실버인지 전혀 모르겠습니다.

 

7. 도서관

https://www.acmicpc.net/problem/1461

1461번: 도서관

체감 난이도 - Medium

 

사과나무 보다는 훨씬 쉽습니다.

 

풀이 사고 과정은 다음과 같습니다.

1 - 책을 한번에 m개씩 운반하는데 m이 n보다 작은 경우에 대하여 운반하는 거리의 2배를 움직여야 합니다. 이유는  운반후 다음으로 운반할 m개를 다시 가지러 0으로 돌아와야 하기 때문.

2 - 유일하게 두배가 되지 않는 경우는 마지막 운반입니다. (제자리로 돌아올 필요가 없기 때문)

3 - 따라서 가장 먼 거리의 운반을 마지막에 하는것이 최적입니다.

4 - 따라서 마지막 배달할 m개를 미리 묶어놓고 나머지를 m개씩 묶습니다.

5 - 4에서 묶는 과정을 양의 좌표와 음의 좌표 따로 해주는게 이득입니다. 한방향으로만 운반을 간다면 가는길에 거쳐가는 위치에는 그냥 떨궈놓고 가면 되지만 두 방향이 섞여 있다면 왔다갔다를 해줘야 해서 거리가 늘어나기 때문입니다.

6 - 즉 m개를 다시 가져갈 필요가 없는 상태로 0을 재방문하는것은 비효율적입니다.

 

그리고 이걸 코드로 짜면 다음과 같습니다.

#include <bits/stdc++.h>
using namespace std;

int n, m;

int ans1, ans2;

vector<int>pos;
vector<int>neg;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for(int i=0; i<n; i++){
        int tmp;
        cin >> tmp;
        if(tmp>0) pos.push_back(tmp);
        else neg.push_back((-1)*tmp);
    }
    sort(pos.begin(), pos.end());
    sort(neg.begin(), neg.end());
    
    int idx1 = ((int)(pos.size()))-1;
    int idx2 = ((int)(neg.size()))-1;
    
    if(neg.empty()||(!pos.empty()&&pos[idx1]>=neg[idx2])){
        ans1 += pos[idx1];
        idx1 -= m;
        for(int i=idx1; i>=0; i-=m){
            ans1 += pos[i]*2;
        }
        for(int i=idx2; i>=0; i-=m){
            ans1 += neg[i]*2;
        }
        cout << ans1;
    }
    else if(pos.empty()||(!neg.empty()&&pos[idx1]<neg[idx2])){
        ans2 += neg[idx2];
        idx2 -= m;
        for(int i=idx1; i>=0; i-=m){
            ans2 += pos[i]*2;
        }
        for(int i=idx2; i>=0; i-=m){
            ans2 += neg[i]*2;
        }
        cout << ans2;
    }
}

양의 좌표나 음의 좌표가 없는 경우를 잘 예외처리 해줘야 합니다.

 

8. 샤워실 바닥 깔기

https://www.acmicpc.net/problem/14601

14601번: 샤워실 바닥 깔기 (Large)

체감 난이도 - Hard

 

어떻게 보면 재귀의 근본이라 볼 수 있는 수학적 귀납법을 사용하는 문제입니다.

즉 우리는 귀납적 증명을 통해 자연수 k에 대하여 한변의 길이가 2^k 인 정사각형을 ㄱ 자 모양 (L트로미노)로 한칸을 비우고 채울수 있음을 보여주고 이를 구현하면 됩니다.

 

1. 양변이 2 (2^1) 인 정사각형은 자명하게 아래와 같이 채울수 있습니다.  

2. 양변이 2^k 인 정사각형을 채울수 있다고 가정해봅시다.

3. 2가 맞다고 가정했을때 2^(k-1)인 정사각형은 아래와 같이 채울수 있게 됩니다. 따라서 귀납적으로 우리는 모든 2^k 크기의 정사각형을 L트로미노로 채울 수 있습니다.

-1 들 자체가 L트로미노를 만들게 됩니다.

이 과정을 코드로 재귀적으로 구현해 보면 다음과 같이 짤수 있습니다.

 

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;

#define endl '\n'
#define flush cout<<flush
#define PRECISION 0

#define fr first 
#define sc second

int n;

int num = 0;

int board[257][257];

bool check(int row, int col, int size){
    for(int i=row; i<row+size; i++){
        for(int j=col; j<col+size; j++){
            if(board[i][j]) return false;
        }
    }
    return true;
}

void solve(int row, int col, int size){
    num++;
    int newsize = size/2;
    if(check(row, col, newsize)) board[row+newsize-1][col+newsize-1]=num;
    if(check(row+newsize, col, newsize)) board[row+newsize][col+newsize-1]=num;
    if(check(row, col+newsize, newsize)) board[row+newsize-1][col+newsize]=num;
    if(check(row+newsize, col+newsize, newsize)) board[row+newsize][col+newsize]=num;
    if(size==2) return;
    solve(row,col,newsize);
    solve(row+newsize,col,newsize);
    solve(row,col+newsize,newsize);
    solve(row+newsize,col+newsize,newsize);
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.setf(ios::fixed); cout.precision(PRECISION);
    cin >> n;
    
    int x, y;
    cin >> x >> y;
    board[y-1][x-1] = -1;
    solve(0,0,(1<<n));
    for(int i=(1<<n)-1; i>=0; i--){
        for(int j=0; j<(1<<n); j++){
            cout << board[i][j] << ' ';
        }
        cout << endl;
    }
}

이상한것들은 무시해주시고 check 함수와 solve함수에 더 집중해주시면 될거 같습니다.

 

참고로 이 문제에서 조심해야 할것은 조건상 1,1이 왼쪽 아래 2^k, 2^k 는 오른쪽 위이지만 배열이 입력을 받는 순서는 그 규칙을 따르지 않습니다.

 

9. 중간

https://www.acmicpc.net/problem/20929

20929번: 중간

체감 난이도 - Hard

 

우선 가장 작은 단위의 문제인 N=1 인 경우 ? A 1 과 ? B 1를 비교한후 둘중 작은 값이 답이 됩니다.

 

그러면 그 외의 경우에는 이 문제를 어떻게 적당히 분할 할수 있을까요?

그 논리는 이분 탐색에서 찾을수 있는데 우선 각 배열이 정렬되어 있는 상태임이 보장될뿐 아니라 배열의 길이는 2^n 의 꼴이기 때문에 이분 탐색을 진행하기 아주 좋은 조건입니다. 

 

우선 배열 A와 배열 B의 N/2번째 값을 확인해줍니다. 이 두 값이 같다면 그 값이 자동으로 합친 배열의 N번째 값이 됩니다.

만약 A[N/2] 가 B[N/2] 보다 작다면 각 배열이 정렬되어 있다는 조건으로 인해 이는 두가지를 의미합니다.
1) 답은 A[N/2+1] 과 A[N] 사이 또는
2) 답은 B[1] 과 B[N/2] 사이에 있다.

 

위 두가지가 성립할수 밖에 없는 이유는 두 배열의 길이가 같고 정렬되어 있기 때문에 만약 A[N/2]가 B[N/2]보다 작다면 A, B를 합친 배열에서는 B[N/2]전에 최소 A의 첫 N/2 원소들과 B의 첫 N/2원소들이 나타나게 됩니다. 따라서 B[N/2]보다 큰 원소들은 전부 답의 후보에서 제외되고 A[N/2]보다 작거나 같은 원소들 또한 답의 후보에서 제외 됩니다.

즉 탐색범위의 중간에 해당하는 값만 비교해줌으로서 우리는 문제를 해결할수 있습니다.

 

더 큰 경우에도 vice versa겠죠.

이렇게 탐색 범위를 절반씩 줄여나가다 보면 언젠가 탐색 범위의 크기가 1 (A의 시작과 끝, B의 시작과 끝이 같은 경우) 가 같은 경우에 도달하게 되는데. 이때 가르키고 있는 A의 값과 B의 값중 작은 값이 답이 됩니다.

작은 값인 이유는 우리가 출력해야 할 값이 중앙값이 아닌 합쳤을때 N번째 값이기 때문입니다.

 

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define flush cout<<flush

int n;

int solve(){
    int st_a=1, st_b=1, en_a=n, en_b=n;
    int median_a;
    int median_b;
    while(1){
        int mida = st_a+en_a>>1;
        int midb = st_b+en_b>>1;
        if(n==1){
            cout << "? A " << st_a << endl;
            flush;
            cin >> median_a;
            cout << "? B " << st_b << endl;
            flush;
            cin >> median_b;
            return min(median_a,median_b);
        }
        if(st_a==en_a && st_b==en_b){
            cout << "? A " << st_a << endl;
            flush;
            cin >> median_a;
            cout << "? B " << st_b << endl;
            flush;
            cin >> median_b;
            return min(median_a,median_b);
        }
        cout << "? A " << mida << endl;
        flush;
        cin >> median_a;
        cout << "? B " << midb << endl;
        flush;
        cin >> median_b;
        if(median_a==median_b){
            return median_a;
        }
        else if(median_a>median_b){
            en_a = mida;
            st_b = midb+1;
        }
        else{
            st_a = mida+1;
            en_b = midb;
        }
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n;
    int ans = solve();
    cout << "! " << ans << endl;
    flush;
}